Question

求最小整数 $k$ ，使得下列条件

$(1)$ $a_1$ ， $a_2$ ， $a_3$ ， $\ldots$ 是一个非递减的正整数数列

$(2)$ $a_n = a_{n-1} + a_{n-2}$ 对所有 $n \gt 2$ 都成立

$(3)$ $a_9 = k$

能同时被不止一个数列满足。

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.

答案

答案：748

知识点：递推斐波那契数列丢番图方程

难度评级：2650

小提示：

反复使用递推式，把目标项表示成前两项： $a_9 = 13a_1 + 21a_2$ 。

Iterate the recurrence to express the target in the first two terms: $a_9 = 13a_1 + 21a_2$

大提示：

若 $13x + 21y = 13u + 21v$ 且 $x \lt u$ ，则 $u - x$ 是 $21$ 的倍数，迫使 $u$ 和 $v$ 至少为 $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$

解答：

反复使用递推式得 $a_9 = 13a_1 + 21a_2$ ，且数列非递减当且仅当 $0 \lt a_1 \le a_2$ （之后的项会自动满足）。因此我们需要找最小的 $k$ ，使得 $13x + 21y = k$ 有两个满足 $0 \lt x \le y$ 的解。

假设 $13x + 21y = 13u + 21v$ 且 $x \lt u$ 。则 $13(u - x) = 21(y - v)$ ，所以 $u - x$ 是 $21$ 的正倍数。因此 $u \ge x + 21 \ge 22$ ，又因为 $u \le v$ ，也有 $v \ge 22$ ，从而 $k = 13u + 21v \ge 34 \cdot 22 = 748$ 。

反过来， $k = 748$ 确实可行： $(x, y) = (1, 35)$ 和 $(22, 22)$ 分别给出数列 $1$ 、 $35$ 、 $36$ 、 $71$ 、 $107$ 、 $178$ 、 $285$ 、 $463$ 、 $748$ ，以及 $22$ 、 $22$ 、 $44$ 、 $66$ 、 $110$ 、 $176$ 、 $286$ 、 $462$ 、 $748$ 。所以答案是 $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 第 8 题

答案：748

难度评级：2650

小提示：

大提示：

解答：

其他年份的第 8 题