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