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

Respuesta: 248

Conceptos:recursión sustitución Teorema chino del resto exponenciación modular

Nivel de dificultad: 3370

Pista pequeña:

La sustitución $y_k = \frac{2x_k - 1}{x_k + 1}$ convierte la recurrencia en $y_{k+1} = y_k^2 - y_k,$ con $y_1 = \frac{13}{12}$

The substitution $y_k = \frac{2x_k - 1}{x_k + 1}$ turns the recurrence into $y_{k+1} = y_k^2 - y_k,$ with $y_1 = \frac{13}{12}$

Pista grande:

Escribiendo $y_k = \frac{c_k}{12^{2^{k-1}}},$ muestra que $x_k = \frac{d + c}{2d - c}$ ya está en su forma más simple, así que $m + n = 3d$

Writing $y_k = \frac{c_k}{12^{2^{k-1}}},$ show $x_k = \frac{d + c}{2d - c}$ is already in lowest terms, so $m + n = 3d$

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}$ Esto se debe a que $y_k - 1 = \frac{x_k - 2}{x_k + 1}.$ Aquí $y_1 = \frac{\frac{39}{11}}{\frac{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 $d$ es divisible por $3$ mientras que $c$ no lo es, así que $d + c$ no es divisible por $3.$ 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$ módulo $4,$ y $2^{20} \equiv 1$ módulo $25$ con $2024 \equiv 4$ módulo $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{\frac{39}{11}}{\frac{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 $d$ is divisible by $3$ while $c$ is not, so $d + c$ is not divisible by $3.$ 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

Respuesta: 248

Nivel de dificultad: 3370

Pista pequeña:

Pista grande:

Solución:

El Problema 13 en otros años