Question

Sea la sucesión de racionales $x_1, x_2, \ldots$ definida de modo que $x_1 = \frac{25}{11}$ y $x_{k+1} = \frac{1}{3}\left(x_k + \frac{1}{x_k} - 1\right)$ para todo $k \ge 1.$ Entonces $x_{2025}$ se puede expresar como $\frac{m}{n}$ para enteros positivos primos entre sí $m$ y $n.$ Halla el residuo cuando $m + n$ se divide entre $1000.$

Let the sequence of rationals $x_1, x_2, \ldots$ be defined such that $x_1 = \frac{25}{11}$ and $x_{k+1} = \frac{1}{3}\left(x_k + \frac{1}{x_k} - 1\right)$ for all $k \ge 1.$ Then $x_{2025}$ can be expressed as $\frac{m}{n}$ for relatively prime positive integers $m$ and $n.$ Find the remainder when $m + n$ is divided by $1000.$

Respuesta

Solución:

Sea $y_k = \frac{2x_k - 1}{x_k + 1}.$ De la recurrencia, $2x_{k+1} - 1 = \frac{(2x_k - 1)(x_k - 2)}{3x_k}$ y $x_{k+1} + 1 = \frac{(x_k + 1)^2}{3x_k},$ así que $\begin{gathered} y_{k+1} = \frac{(2x_k - 1)(x_k - 2)}{(x_k + 1)^2} \\ = y_k(y_k - 1) = y_k^2 - y_k, \end{gathered}$ ya que $y_k - 1 = \frac{x_k - 2}{x_k + 1}.$ Aquí $y_1 = \frac{39/11}{36/11} = \frac{13}{12}.$ Por inducción $y_k = \frac{c_k}{12^{2^{k-1}}}$ donde $c_1 = 13$ y $c_{k+1} = c_k\bigl(c_k - 12^{2^{k-1}}\bigr);$ como $12^{2^{k-1}}$ es divisible por $6,$ cada $c_k$ permanece coprimo con $6.$

Invirtiendo la sustitución, $x_k = \frac{1 + y_k}{2 - y_k} = \frac{d + c}{2d - c}$ con $d = 12^{2^{k-1}}$ y $c = c_k.$ Todos los $x_k$ son positivos (para $x \gt 0,$ $x + \frac{1}{x} - 1 \ge 1$ ), así que $y_k = \frac{2x_k - 1}{x_k + 1} \in (-1, 2),$ haciendo que tanto $d + c$ como $2d - c$ sean positivos. Cualquier divisor común de $d + c$ y $2d - c$ divide a sus combinaciones $3d$ y $3c;$ como $\gcd(c, d) = 1,$ divide a $3,$ pero $3 \mid d$ y $3 \nmid c,$ así que $3 \nmid d + c.$ Por lo tanto la fracción está en su forma más simple y $m + n = 3d = 3 \cdot 12^{2^{2024}}.$

Módulo $8,$ $12^{2^{2024}} \equiv 0.$ Módulo $125,$ el orden multiplicativo de $12$ divide a $\lambda(125) = 100,$ y $2^{2024} \equiv 16 \pmod{100}$ (es $0$ mod $4,$ y $2^{20} \equiv 1$ mod $25$ con $2024 \equiv 4$ mod $20$ ), así que $12^{2^{2024}} \equiv 12^{16} \equiv 41 \pmod{125}.$ El teorema chino del resto da $12^{2^{2024}} \equiv 416 \pmod{1000},$ así que $m + n \equiv 3 \cdot 416$ $= 1248 \equiv 248 \pmod{1000}.$

Let $y_k = \frac{2x_k - 1}{x_k + 1}.$ From the recurrence, $2x_{k+1} - 1 = \frac{(2x_k - 1)(x_k - 2)}{3x_k}$ and $x_{k+1} + 1 = \frac{(x_k + 1)^2}{3x_k},$ so $\begin{gathered} y_{k+1} = \frac{(2x_k - 1)(x_k - 2)}{(x_k + 1)^2} \\ = y_k(y_k - 1) = y_k^2 - y_k, \end{gathered}$ since $y_k - 1 = \frac{x_k - 2}{x_k + 1}.$ Here $y_1 = \frac{39/11}{36/11} = \frac{13}{12}.$ By induction $y_k = \frac{c_k}{12^{2^{k-1}}}$ where $c_1 = 13$ and $c_{k+1} = c_k\bigl(c_k - 12^{2^{k-1}}\bigr);$ since $12^{2^{k-1}}$ is divisible by $6,$ every $c_k$ stays coprime to $6.$

Inverting the substitution, $x_k = \frac{1 + y_k}{2 - y_k} = \frac{d + c}{2d - c}$ with $d = 12^{2^{k-1}}$ and $c = c_k.$ All $x_k$ are positive (for $x \gt 0,$ $x + \frac{1}{x} - 1 \ge 1$ ), so $y_k = \frac{2x_k - 1}{x_k + 1} \in (-1, 2),$ making both $d + c$ and $2d - c$ positive. Any common divisor of $d + c$ and $2d - c$ divides their combinations $3d$ and $3c;$ as $\gcd(c, d) = 1,$ it divides $3,$ but $3 \mid d$ and $3 \nmid c,$ so $3 \nmid d + c.$ Hence the fraction is in lowest terms and $m + n = 3d = 3 \cdot 12^{2^{2024}}.$

Modulo $8,$ $12^{2^{2024}} \equiv 0.$ Modulo $125,$ the multiplicative order of $12$ divides $\lambda(125) = 100,$ and $2^{2024} \equiv 16 \pmod{100}$ (it is $0$ mod $4,$ and $2^{20} \equiv 1$ mod $25$ with $2024 \equiv 4$ mod $20$ ), so $12^{2^{2024}} \equiv 12^{16} \equiv 41 \pmod{125}.$ The Chinese remainder theorem gives $12^{2^{2024}} \equiv 416 \pmod{1000},$ so $m + n \equiv 3 \cdot 416$ $= 1248 \equiv 248 \pmod{1000}.$

2025 AIME II Problema 13

Solución:

El Problema 13 en otros años