Skip to main content

2013 AMC 10B Problem 21

Problem 21 of 25HarderAlgebraNumber TheoryProblem-Solving Techniques

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(b1−a1)=8(a2−b2)5(b_1-a_1)=8(a_2-b_2). Since 55 and 88 are relatively prime, b1−a1b_1-a_1 is at least 88, and then nondecreasing order gives b2≥b1≥a1+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=5⋅0+8⋅13=104N=5\cdot0+8\cdot13=104. Thus, the correct answer is C .
AoPS wiki

Tagged: Fibonacci · Diophantine Equation · optimization

More practice