2013 AIME I Problem 15

Below is the professionally curated solution for Problem 15 of the 2013 AIME I, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:arithmetic sequencemodular arithmeticcounting pairs

Difficulty rating: 3270

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.

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+2D=5+3j+6k99,C = A + 2D = 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.N = \sum_{k=0}^{15} (32 - 2k) = 16 \cdot 32 - 2 \cdot \frac{15 \cdot 16}{2} = 512 - 240 = 272.

← Problem 14Full Exam

Problem 15 in Other Years