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

0A<B<C99,0 \le A \lt B \lt C \le 99,

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

pp divides Aa,A - a, Bb,B - b, and Cc,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
Solution:

Let dd be the common difference of (b,a,c),(b, a, c), so ab=ca=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=BAba=dD = B - A \equiv b - a = -d and D=CBcb=2d,D = C - B \equiv c - b = 2d, so p3d.p \mid 3d. 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 A1,A \equiv 1, B0,B \equiv 0, C2(mod3).C \equiv 2 \pmod 3. Write A=1+3jA = 1 + 3j with j0;j \ge 0; the difference satisfies D12(mod3),D \equiv -1 \equiv 2 \pmod 3, so D=2+3kD = 2 + 3k with k0.k \ge 0. The constraint is C=A+2DC = A + 2D =5+3j+6k99,= 5 + 3j + 6k \le 99, i.e. j+2k31,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 322k32 - 2k choices of j,j, so N=k=015(322k)=1632215162=512240=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