Skip to main content

2013 AMC 10B Problem 21

Problem 21 of 25HarderAlgebraNumber Theory

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.N. What is the smallest possible value of NN ?

Answer choices

Show solution

Solution

A sequence starting with u,vu,v has seventh term 5u+8v5u+8v. For two sequences (a1,a2)(a_1,a_2) and (b1,b2)(b_1,b_2) with different first terms, assume a1<b1a_1\lt b_1. Then 5a1+8a2=5b1+8b25a_1+8a_2=5b_1+8b_2, so 5(b1a1)=8(a2b2)5(b_1-a_1)=8(a_2-b_2). Since 55 and 88 are relatively prime, b1a1b_1-a_1 is at least 88, and then nondecreasing order gives b2b1a1+8b_2\ge b_1\ge a_1+8. The smallest construction is a1=0a_1=0, b1=b2=8b_1=b_2=8, and a2=13a_2=13. This gives N=50+813=104N=5\cdot0+8\cdot13=104. Thus, the correct answer is C .

More practice

Concepts: Fibonacci · Diophantine Equation · optimization

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.