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 题