2021 AIME I Problem 10

Attempt Problem 10 of the 2021 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 2021 AIME I solutions, or check the answer key.

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

10.

Consider the sequence (ak)k1(a_k)_{k \ge 1} of positive rational numbers defined by a1=20202021a_1 = \frac{2020}{2021} and for k1,k \ge 1, if ak=mna_k = \frac{m}{n} for relatively prime positive integers mm and n,n, then ak+1=m+18n+19.a_{k+1} = \frac{m + 18}{n + 19}. Determine the sum of all positive integers jj such that the rational number aja_j can be written in the form tt+1\frac{t}{t+1} for some positive integer t.t.

Answer: 59
Concepts:greatest common divisorrecursioninvariant
Difficulty rating: 2990
Solution:

Write ak=mna_k = \frac{m}{n} in lowest terms and let d=nm,d = n - m, so aja_j has the form tt+1\frac{t}{t+1} exactly when d=1.d = 1. One step sends (m,n)(m, n) to (m+18,n+19)(m + 18,\, n + 19) and then cancels g=gcd(m+18,n+19).g = \gcd(m + 18, n + 19). Two facts control everything. First, I=19m18nI = 19m - 18n satisfies 19(m+18)18(n+19)=I,19(m + 18) - 18(n + 19) = I, so II is unchanged by the shift and divided by gg upon cancellation. Second, since I=19(m+18)18(n+19)I = 19(m + 18) - 18(n + 19) =(m+18)18(d+1),= (m + 18) - 18(d + 1), a number divides both m+18m + 18 and n+19n + 19 exactly when it divides both d+1d + 1 and I;I; hence g=gcd(d+1,I),g = \gcd(d + 1,\, I), and after cancelling, the new difference is d+1g.\frac{d + 1}{g}.

Initially I=192020182021=2002I = 19 \cdot 2020 - 18 \cdot 2021 = 2002 =271113= 2 \cdot 7 \cdot 11 \cdot 13 and d=1,d = 1, so j=1j = 1 works. The next step has d+1=2,d + 1 = 2, g=2:g = 2: a2=20382040=10191020,a_2 = \frac{2038}{2040} = \frac{1019}{1020}, so j=2j = 2 works and I=1001=71113.I = 1001 = 7 \cdot 11 \cdot 13. From there dd climbs 1,2,3,1, 2, 3, \ldots until d+1d + 1 shares a factor with I:I: at d+1=7d + 1 = 7 we get a8=161162a_8 = \frac{161}{162} (cancel 7,7, now I=143I = 143); then at d+1=11,d + 1 = 11, a18=3132a_{18} = \frac{31}{32} (cancel 11,11, now I=13I = 13); then at d+1=13,d + 1 = 13, a30=1920a_{30} = \frac{19}{20} (cancel 13,13, now I=1I = 1). Each cancellation used g=d+1,g = d + 1, so dd returned to 11 at j=8,j = 8, 18,18, and 30.30.

Once I=1,I = 1, no further cancellation is possible, so dd increases forever and never equals 11 again. The valid indices are j=1,2,8,18,30,j = 1, 2, 8, 18, 30, with sum 1+2+8+18+30=59.1 + 2 + 8 + 18 + 30 = 59.

← Problem 9#9
Full Exam

Problem 10 in Other Years