Question

Considere la sucesión $(a_k)_{k \ge 1}$ de números racionales positivos definida por $a_1 = \frac{2020}{2021}$ y, para $k \ge 1,$ si $a_k = \frac{m}{n}$ con $m$ y $n$ enteros positivos primos entre sí, entonces $a_{k+1} = \frac{m + 18}{n + 19}.$ Determine la suma de todos los enteros positivos $j$ tales que el número racional $a_j$ se puede escribir en la forma $\frac{t}{t+1}$ para algún entero positivo $t.$

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

Respuesta

Solución:

Escriba $a_k = \frac{m}{n}$ en su forma más simple y sea $d = n - m,$ de modo que $a_j$ tiene la forma $\frac{t}{t+1}$ exactamente cuando $d = 1.$ Un paso lleva $(m, n)$ a $(m + 18,\, n + 19)$ y luego cancela $g = \gcd(m + 18, n + 19).$ Dos hechos controlan todo. Primero, $I = 19m - 18n$ satisface $19(m + 18) - 18(n + 19) = I,$ así que $I$ no cambia con el desplazamiento y se divide por $g$ al cancelar. Segundo, como $I = 19(m + 18) - 18(n + 19)$ $= (m + 18) - 18(d + 1),$ un número divide a la vez a $m + 18$ y a $n + 19$ exactamente cuando divide a la vez a $d + 1$ y a $I;$ por lo tanto $g = \gcd(d + 1,\, I),$ y tras cancelar, la nueva diferencia es $\frac{d + 1}{g}.$

Inicialmente $I = 19 \cdot 2020 - 18 \cdot 2021 = 2002$ $= 2 \cdot 7 \cdot 11 \cdot 13$ y $d = 1,$ así que $j = 1$ funciona. El siguiente paso tiene $d + 1 = 2,$ $g = 2:$ $a_2 = \frac{2038}{2040} = \frac{1019}{1020},$ así que $j = 2$ funciona e $I = 1001 = 7 \cdot 11 \cdot 13.$ A partir de ahí $d$ sube $1, 2, 3, \ldots$ hasta que $d + 1$ comparte un factor con $I:$ en $d + 1 = 7$ obtenemos $a_8 = \frac{161}{162}$ (cancelamos $7,$ ahora $I = 143$ ); luego en $d + 1 = 11,$ $a_{18} = \frac{31}{32}$ (cancelamos $11,$ ahora $I = 13$ ); luego en $d + 1 = 13,$ $a_{30} = \frac{19}{20}$ (cancelamos $13,$ ahora $I = 1$ ). Cada cancelación usó $g = d + 1,$ así que $d$ volvió a $1$ en $j = 8,$ $18,$ y $30.$

Una vez que $I = 1,$ no es posible ninguna cancelación más, así que $d$ aumenta para siempre y nunca vuelve a valer $1$ de nuevo. Los índices válidos son $j = 1, 2, 8, 18, 30,$ con suma $1 + 2 + 8 + 18 + 30 = 59.$

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

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

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

2021 AIME I Problema 10

Solución:

El Problema 10 en otros años