[Soln] 2013 AIME I Problem 15

2013 AIME I 15. Let N be the number of ordered triples (A, B, C) of integers satisfying the conditions

(a) 0 \leq A < B < C \leq 99,
(b) there exist integers a, b, and c, and prime p where 0 \leq b < a < c < p,
(c) p divides A - a, B - b, and C - c, and
(d) each ordered triple (A, B, C) and each ordered triple (b, a, c) form arithmetic sequences.

Find N.


There are many variables in this problem, with some of them ordered in a non-traditional way (see (b)). Let’s try to lay them out in a way that makes sense:

AIME_I_2016_15_01

Here, we’ve put (a) and (b) in a diagram. The next bit of information we’ll put into the diagram is (d). Since we are working with triplets forming arithmetic sequences, I prefer to have them in the form a-d, a, a+d instead of a, a+d, a+2d. This is because the former has symmetry which allows it to sum to 3a, while the latter sums to the uglier 3a + 3d. Let’s put this information in:

AIME_I_2016_15_02

(Note that R and r must both be positive, and that 2r < p.) Now, let’s write out the 3 expressions that are supposed to be divisible by p:

AIME_I_2016_15_03

 

A natural next move is to manipulate the relations (1), (2) and (3) to isolate variables on the right; this will (hopefully) restrict the choices for p. There are a lot of similarities on the RHSes of the 3 relations so we can hope that something simple comes out of it.

(2) - (1) gives

p \mid R + r, \hspace{2em}-(4)

and (3) - (2) gives

p \mid R - 2r. \hspace{2em}-(5)

The R term is repeated in the 2 relations above! We can subtract one from the other to obtain

\begin{aligned} p &\mid (R+r) - (R-2r), \\  p &\mid 3r. \end{aligned}

Remember that 0 < r < p? This means that p is relatively prime to r, and so

p \mid 3, i.e. p = 3.

This is a big result! Because of condition (b), we must have b = 0, a = 1, c = 2 and r = 1. Let’s update our variable diagram:

AIME_I_2016_15_04

The new (2) is the easiest to make sense of: B must be a multiple of 3. For each value of B, we can list the admissible values of A and C:

AIME_I_2016_15_05

At first, as B increases, the number of possible triplets increases. For each B, the thing that is stopping more possible triplets is hitting up against the constraint that A \geq 0. However, at some point as B gets too big, the constraint we hit up against first is C \leq 99.

Where does this happen? One might imagine that it happens somewhere in the middle:

If B = 48, then when A = 1, we have C = 48 \times 2 - 1 = 95 which is admissible. Hence, the constraint we hit first is still A \geq 0.

If B = 51, then when A = 1, we have C = 51 \times 2 - 1 = 101 which is inadmissible. Hence the constraint we hit first is now C \leq 99.

Now, note that every time B increases from 3 to 48, the number of possibilities increases in increments of 1, from 1 to 16. In the other direction, as B decreases from 96 to 51, the number of possibilities increases in increments of 1, from 1 to 16. Putting all this together, the number of possible (A, B, C) triplets is

\begin{aligned} N &= (1 + 2 + \dots + 15 + 16) + (16 + 15 + 14 + \dots + 2 + 1) \\  &= \frac{16 \cdot 17}{2} \times 2 \\  &= \fbox{272}.\end{aligned}

Done!

Advertisements
This entry was posted in Grade 12, USA and tagged , , . Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s