AMC 10 · 2013 · #14

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 different climbing sequences follow the same adding rule and share a later term. Find the smallest shared value.

Pick an answer.

(A)

(B)

(C)

104

(D)

144

(E)

273

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

The shared term is a linear expression.

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

2STEP 2

Two sequences, one value of N

Equal values give one equation.

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

3STEP 3

The smallest step between solutions

Coprime coefficients fix the smallest step.

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

4STEP 4

Apply the ordering rule and minimize

The climbing rule then bounds the start.

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

5STEP 5

Check both sequences and read off N

The smallest shared value is 104, choice (E).

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

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