Question

求满足下列条件的最小整数 $k$ ：

• $a_1, a_2, a_3, \ldots$ 是一个非递减的正整数数列

• 对所有 $n \gt 2$ ，都有 $a_n = a_{n-1} + a_{n-2}$

• $a_9 = k$

并且满足这些条件的数列不止一个。

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.

答案

答案：748

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

难度评级：2650

解答：

反复使用递推式得 $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 题