2013 AIME I Problem 15

Attempt Problem 15 of the 2013 AIME I below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2013 AIME I solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

15.

Let NN be the number of ordered triples (A,B,C)(A, B, C) of integers satisfying the conditions

• 0≤A<B<C≤99,0 \le A \lt B \lt C \le 99,

• there exist integers a,a, b,b, and c,c, and prime pp where 0≤b<a<c<p,0 \le b \lt a \lt c \lt p,

• pp divides A−a,A - a, B−b,B - b, and C−c,C - c, and

• each ordered triple (A,B,C)(A, B, C) and each ordered triple (b,a,c)(b, a, c) form arithmetic sequences.

Find N.N.

Answer: 272
Concepts:arithmetic sequencemodular arithmeticcounting pairs
Difficulty rating: 3270
Small Hint:

If DD and dd are the common differences of (A,B,C)(A,B,C) and (b,a,c),(b,a,c), then mod pp both D≡−dD \equiv -d and D≡2d,D \equiv 2d, so 3d3d is divisible by pp

Big Hint:

Since 0<2d<p,0 \lt 2d \lt p, that forces p=3p = 3 and (b,a,c)=(0,1,2);(b,a,c) = (0,1,2); count triples with A≡1,A \equiv 1, B≡0,B \equiv 0, C≡2(mod3)C \equiv 2 \pmod 3

Solution:

Let dd be the common difference of (b,a,c),(b, a, c), so a−b=c−a=d>0a - b = c - a = d \gt 0 and c=b+2d<p,c = b + 2d \lt p, whence 0<2d<p.0 \lt 2d \lt p. Let D>0D \gt 0 be the common difference of (A,B,C).(A, B, C). Reducing mod p,p, we get D=B−A≡b−a=−dD = B - A \equiv b - a = -d and D=C−B≡c−b=2d,D = C - B \equiv c - b = 2d, so 3d3d is divisible by p.p. Since 0<d<p,0 \lt d \lt p, the prime pp cannot divide d,d, so p=3;p = 3; then 2d<32d \lt 3 gives d=1d = 1 and (b,a,c)=(0,1,2).(b, a, c) = (0, 1, 2).

So the valid triples are exactly the increasing arithmetic progressions in [0,99][0, 99] with A≡1,A \equiv 1, B≡0,B \equiv 0, C≡2(mod3).C \equiv 2 \pmod 3. Write A=1+3jA = 1 + 3j with j≥0;j \ge 0; the difference satisfies D≡−1≡2(mod3),D \equiv -1 \equiv 2 \pmod 3, so D=2+3kD = 2 + 3k with k≥0.k \ge 0. The constraint is C=A+2DC = A + 2D =5+3j+6k≤99,= 5 + 3j + 6k \le 99, i.e. j+2k≤31,j + 2k \le 31, and every such pair (j,k)(j, k) works.

For each k=0,1,…,15k = 0, 1, \ldots, 15 there are 32−2k32 - 2k choices of j,j, so N=∑k=015(32−2k)=16⋅32−2⋅15⋅162=512−240=272. \begin{aligned} &N = \sum_{k=0}^{15} (32 - 2k) \\ &= 16 \cdot 32 - 2 \cdot \frac{15 \cdot 16}{2} \\ &= 512 - 240 = 272. \end{aligned}

Problem 14#14
Full Exam

Problem 15 in Other Years