2021 AIME I Problem 10

Below is the professionally curated solution for Problem 10 of the 2021 AIME I, 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 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:greatest common divisorrecursioninvariant

Difficulty rating: 2990

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.

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)=(m+18)18(d+1),I = 19(m + 18) - 18(n + 19) = (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=2002=271113I = 19 \cdot 2020 - 18 \cdot 2021 = 2002 = 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 9Full ExamProblem 11

Problem 10 in Other Years