Question

Halle el menor entero

k

para el cual las condiciones

(1)

a_1,

a_2,

a_3,

\ldots

es una sucesión no decreciente de enteros positivos

(2)

a_n = a_{n-1} + a_{n-2}

para todo

n \gt 2

(3)

a_9 = k

se cumplen para más de una sucesión.

Find the smallest integer

k

for which the conditions

(1)

a_1,

a_2,

a_3,

\ldots

is a nondecreasing sequence of positive integers

(2)

a_n = a_{n-1} + a_{n-2}

for all

n \gt 2

(3)

a_9 = k

are satisfied by more than one sequence.

Respuesta

Respuesta: 748

Conceptos:recursión Fibonacci Ecuación diofántica

Nivel de dificultad: 2650

Pista pequeña:

Itere la recurrencia para expresar el objetivo en los dos primeros términos:

a_9 = 13a_1 + 21a_2

Iterate the recurrence to express the target in the first two terms:

a_9 = 13a_1 + 21a_2

Pista grande:

Si

13x + 21y = 13u + 21v

con

x \lt u,

entonces

u - x

es un múltiplo de

21,

forzando a que

u

y

v

sean al menos

22

If

13x + 21y = 13u + 21v

with

x \lt u,

then

u - x

is a multiple of

21,

forcing

u

and

v

to be at least

22

Solución:

Iterando la recurrencia se obtiene

a_9 = 13a_1 + 21a_2,

y la sucesión es no decreciente exactamente cuando

0 \lt a_1 \le a_2

(todos los términos posteriores se acomodan por sí solos). Así que necesitamos el menor

k

para el cual

13x + 21y = k

tiene dos soluciones con

0 \lt x \le y.

Supongamos

13x + 21y = 13u + 21v

con

x \lt u.

Entonces

13(u - x) = 21(y - v),

así que

u - x

es un múltiplo positivo de

21.

Por tanto

u \ge x + 21 \ge 22,

y como

u \le v,

también

v \ge 22,

lo que da

k = 13u + 21v \ge 34 \cdot 22 = 748.

Recíprocamente

k = 748

funciona:

(x, y) = (1, 35)

y

(22, 22)

dan las sucesiones

1,

35,

36,

71,

107,

178,

285,

463,

748

y

22,

22,

44,

66,

110,

176,

286,

462,

748.

La respuesta es

k = 748.

Iterating the recurrence gives

a_9 = 13a_1 + 21a_2,

and the sequence is nondecreasing exactly when

0 \lt a_1 \le a_2

(all later terms then take care of themselves). So we need the smallest

k

for which

13x + 21y = k

has two solutions with

0 \lt x \le y.

Suppose

13x + 21y = 13u + 21v

with

x \lt u.

Then

13(u - x) = 21(y - v),

so

u - x

is a positive multiple of

21.

Hence

u \ge x + 21 \ge 22,

and since

u \le v,

also

v \ge 22,

giving

k = 13u + 21v \ge 34 \cdot 22 = 748.

Conversely

k = 748

works:

(x, y) = (1, 35)

and

(22, 22)

give the sequences

1,

35,

36,

71,

107,

178,

285,

463,

748

and

22,

22,

44,

66,

110,

176,

286,

462,

748.

The answer is

k = 748.

2002 AIME I Problema 8

Respuesta: 748

Nivel de dificultad: 2650

Pista pequeña:

Pista grande:

Solución:

El Problema 8 en otros años