AMC 10 · 2013 · #21

Grade 7 counting
Archetype Small-Domain Constrained Search └ Sub-archetype Sum-Target Search
recursive-sequencelinear-diophantinegcd extremal-constructionpattern-recognition ↑ Prerequisites: gcd
📏 Medium solution 💡 3 insights
Problem
Two sequences of nonnegative integers are each non-decreasing, and each follows the Fibonacci-style rule that from the third term on, every term is the sum of the two before it. The two sequences have different first terms, yet the seventh term of each sequence is the same number N. What is the smallest possible value of N?

Pick an answer.

(A)
55
(B)
89
(C)
104
(D)
144
(E)
273

AMC 10 2013 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve
Strategy Extreme Principle

The phrase 'smallest possible value' is a direct call for the Extreme Principle: push N as low as it can go while everything still holds. First name the two starting terms a and b so the seventh term becomes a clean formula in a and b. That formula turns 'two sequences with the same seventh term' into 'two different (a, b) pairs giving the same number', and the Extreme Principle then chases the smallest such number allowed by the ordering rule a ＜ = b.

1STEP 1

Write the seventh term with variables

Name the first two terms a and b; the rule builds a, b, a+b, a+2b, 2a+3b, 3a+5b, so the seventh term is N = 5a + 8b.

a, b, a+b, a+2b, 2a+3b, 3a+5b, 5a+8b → N = 5a + 8b
2STEP 2

Two sequences, one value of N

Sharing the seventh term means 5a + 8b = 5a' + 8b', so 5(a' - a) = 8(b - b'), and neither side is zero because a and a' differ.

5a + 8b = 5a' + 8b' ⟹ 5(a' - a) = 8(b - b')
3STEP 3

The smallest step between solutions

Since 5 and 8 share no factor, a' - a must be a multiple of 8 and b - b' a multiple of 5, so the smallest jump is (a + 8, b - 5).

gcd(5,8)=1 → a' = a + 8, b' = b - 5
4STEP 4

Apply the ordering rule and minimize

Non-decreasing forces a + 8 ≤ b - 5, so b ≥ a + 13; minimizing N = 5a + 8b then pins a = 0, b = 13.

a + 8 ≤ b - 5 → b ≥ a + 13; min N at a=0, b=13
5STEP 5

Check both sequences and read off N

Pair (0, 13) gives 0, 13, 13, 26, 39, 65, 104 and pair (8, 8) gives 8, 8, 16, 24, 40, 64, 104 — different starts, same seventh term 104.

N = 5(0) + 8(13) = 104 = 5(8) + 8(8)
Answer
104
The bound is tight from both sides: N = 5a + 8b with the forced gap b ≥ a + 13 cannot dip below 5(0) + 8(13) = 104, and the concrete pair of sequences 0,13,...,104 and 8,8,...,104 shows 104 is achieved with different first terms. The smaller options 55 and 89 are Fibonacci numbers reachable by only one natural pair, so they cannot come from two different starts; 104 is the first value expressible as 5a + 8b in two ordered ways.
💡Key takeaway

Turn the seventh term into the formula 5a + 8b, then push the two starting numbers as low as the rising-order rule allows to find the smallest shared value.

  • Write the seventh term with variables
  • Two sequences, one value of N
  • The smallest step between solutions
  • Apply the ordering rule and minimize
  • Check both sequences and read off N

More like this

Same archetype — closest grade level first.