2002 AIME I Problem 8

Question

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.

Answer

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

a_9 = 13a_1 + 21a_2

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

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.

Problem 8 in other years