## [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:

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:

(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$:

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:

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$:

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!