2013 AMC 10B Problem 21

Question

Two non-decreasing sequences of nonnegative integers have different first terms. Each sequence has the property that each term beginning with the third is the sum of the previous two terms, and the seventh term of each sequence is

N.

What is the smallest possible value of

N

?

55

89

104

144

273

Answer: C

Concepts:Fibonacci Diophantine Equation optimization

Difficulty rating: 2010

Small hint:

Write the seventh term in terms of the first two terms

Big hint:

Use divisibility by

8

and

5

to force the smallest distinct starts

Solution:

A sequence starting with

u,v

has seventh term

5u+8v

.

For two sequences

(a_1,a_2)

and

(b_1,b_2)

with different first terms, assume

a_1\lt b_1

. Then

5a_1+8a_2=5b_1+8b_2

, so

5(b_1-a_1)=8(a_2-b_2)

.

Since

5

and

8

are relatively prime,

b_1-a_1

is at least

8

, and then nondecreasing order gives

b_2\ge b_1\ge a_1+8

.

The smallest construction is

a_1=0

,

b_1=b_2=8

, and

a_2=13

. This gives

N=5\cdot0+8\cdot13=104

.

Thus, the correct answer is C .