2016 AIME II Problem 9

Attempt Problem 9 of the 2016 AIME II 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 2016 AIME II solutions, or check the answer key.

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

9.

The sequences of positive integers 1,a2,a3,1, a_2, a_3, \ldots and 1,b2,b3,1, b_2, b_3, \ldots are an increasing arithmetic sequence and an increasing geometric sequence, respectively. Let cn=an+bn.c_n = a_n + b_n. There is an integer kk such that ck1=100c_{k-1} = 100 and ck+1=1000.c_{k+1} = 1000. Find ck.c_k.

Answer: 262
Concepts:arithmetic sequencegeometric sequencemodular arithmeticcasework
Difficulty rating: 2920
Solution:

Write an=1+(n1)da_n = 1 + (n-1)d and bn=rn1b_n = r^{n-1} with integers d1d \ge 1 and r2.r \ge 2. Since c1=2<100,c_1 = 2 \lt 100, we have k3,k \ge 3, and the two conditions read (k2)d+rk2=99,(k-2)d + r^{k-2} = 99, kd+rk=999.kd + r^k = 999.

Subtracting, 2d+rk3(r1)r(r+1)=900.2d + r^{k-3}(r-1)r(r+1) = 900. The product of three consecutive integers is divisible by 3,3, so 32d,3 \mid 2d, hence 3d.3 \mid d. Then (k2)d+rk2=99(k-2)d + r^{k-2} = 99 forces 3rk2,3 \mid r^{k-2}, so 3r.3 \mid r. The bounds rk298r^{k-2} \le 98 and rk998r^k \le 998 leave only (r,k)=(3,3),(r, k) = (3, 3), (3,4),(3, 4), (3,5),(3, 5), (3,6),(3, 6), (6,3),(6, 3), (9,3).(9, 3).

Testing each against (k2)d=99rk2(k-2)d = 99 - r^{k-2} and kd=999rk,kd = 999 - r^k, only (r,k)=(9,3)(r, k) = (9, 3) gives a consistent value, d=90.d = 90. Then c3=1+290+92=262.c_3 = 1 + 2 \cdot 90 + 9^2 = 262.

← Problem 8#8
Full Exam

Problem 9 in Other Years