Skip to main content

2013 AMC 12B Problem 14

Problem 14 of 25IntermediateAlgebraNumber 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 N?N?

Answer choices

Show solution

Solution

A sequence starting a1,a2a_1, a_2 has seventh term 5a1+8a2.5a_1 + 8a_2. For the two sequences, 5a1+8a2=5b1+8b2,5a_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 gcd⁡(5,8)=1,\gcd(5, 8) = 1, we need b1−a1b_1 - a_1 to be a multiple of 88 and a2−b2a_2 - b_2 to be a multiple of 5.5. Taking a1<b1a_1 \lt b_1 with nondecreasing terms gives a1≤b1−8≤b2−8≤a2−13.a_1 \le b_1 - 8 \le b_2 - 8 \le a_2 - 13. Choosing a1=0,a_1 = 0, b1=b2=8,b_1 = b_2 = 8, a2=13a_2 = 13 yields N=5⋅0+8⋅13=104.N = 5\cdot 0 + 8\cdot 13 = 104. Thus, the correct answer is C.
AoPS wiki

Tagged: Fibonacci · Diophantine Equation · greatest common divisor

More practice