Question

Halle el menor entero $k$ para el cual las condiciones

• $a_1, a_2, a_3, \ldots$ es una sucesión no decreciente de enteros positivos

• $a_n = a_{n-1} + a_{n-2}$ para todo $n \gt 2$

• $a_9 = k$

se satisfacen por más de una sucesión.

Find the smallest integer $k$ for which the conditions

• $a_1, a_2, a_3, \ldots$ is a nondecreasing sequence of positive integers

• $a_n = a_{n-1} + a_{n-2}$ for all $n \gt 2$

• $a_9 = k$

are satisfied by more than one sequence.

Respuesta

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

Solución:

El Problema 8 en otros años