AMC 10 · 2006 · #23

Grade 9 algebrapattern

Archetype Lattice / Grid Pattern from Small Cases └ Sub-archetype Figure-N Growth Sequence

sequences-geometricrecursive-sequenceexponents easier-related-problemwork-backwards ↑ Prerequisites: sequences-geometricexponents

📏 Long solution 💡 3 insights

Problem

A list of powers is repeatedly replaced by the averages of neighbouring pairs, one hundred times. The single surviving number is a given power of one half. Find the base of the original powers.

Pick an answer.

(A)

$1-\frac{\sqrt{2}}{2}$

(B)

$\sqrt{2}-1$

(C)

$\frac{1}{2}$

(D)

$2-\sqrt{2}$

(E)

$\frac{\sqrt{2}}{2}$

How to solve

Strategy Solve an Easier Related Problem

Nobody can carry out 100 rounds of averaging by hand, so do one round instead (Tool #9) and look at what comes back. Because S is geometric, neighbouring terms differ by exactly one factor of x, so their average keeps the factor x^i-1 and picks up the constant (1+x)/2. One round therefore returns a shorter copy of the same kind of list. That self-similarity is the hinge: it means round 2 faces the same situation as round 1, so the single one-line computation covers all 100 rounds. Turning that observation into a formula for every m is where the argument has to be tight (Tool #5) — reading the pattern off m=1 and m=2 and writing 'in general' is not a proof, and the fix costs one extra sentence. Split the work first (Tool #7): count how many terms survive, then find what the survivor equals. With the closed form in hand, the given output value lets you run the machine in reverse to get an equation for x (Tool #11). Solving that equation is the second place to be careful: regroup the exponent (Tool #15) so the equation becomes a square, use x ＞ 0 to throw out the root that does not qualify (Tool #3), and then substitute the candidate back through the whole machine (Tool #6) so the answer is verified, not merely forced.

1STEP 1

Count the terms and the rounds

Each round shortens the list, so a hundred rounds leave one number.

n=101; length of A^m(S) is 101-m; length of A¹⁰⁰(S) is 1

2STEP 2

Do one round and watch the shape survive

One round factors out a constant and keeps the same shape.

(x^i-1+x^i)/2=x^i-1·(1+x)/2 → A(S)=(1+x)/2·(1,x,x²,… ,x⁹⁹)

3STEP 3

Repeat the same one-line move

So the move simply repeats, giving a clean closed form.

A^m(S)=((1+x)/2)^m(1,x,… ,x¹00-m) → A¹⁰⁰(S)=(((1+x)/2)¹⁰⁰)

4STEP 4

Work backwards from the final number

Working backwards turns the final value into one power equation.

((1+x)/2)¹⁰⁰=1/2⁵⁰⇔((1+x)¹⁰⁰)/2¹⁰⁰=1/2⁵⁰⇔ (1+x)¹⁰⁰=2⁵⁰

5STEP 5

Regroup the exponent, then compare sizes

Regrouping the exponent lets the powers be compared.

((1+x)²)⁵⁰=2⁵⁰, and u↦ u⁵⁰ is one-to-one for u ＞ 0, so (1+x)²=2

6STEP 6

Keep only the root that positivity allows

Positivity kills one root, leaving √(2)-1.

(1+x)²=2 → 1+x=±√(2); x ＞ 0 kills 1+x=-√(2), leaving x=√(2)-1

7STEP 7

Check the candidate end to end

Checking it end to end confirms √(2)-1, choice (B).

(1+x)/2=√(2)/2 and (√(2)/2)¹⁰⁰=2⁵⁰/2¹⁰⁰=1/2⁵⁰ → (B)

Answer

√(2)-1

Three checks. First, size: the surviving number is r¹⁰⁰ where r=(1+x)/2, and it has to equal 1/2⁵⁰≈ 8.9 × 10⁻¹⁶. Shrinking to that in 100 steps needs r a little above 0.7, which matches r=√(2)/2≈ 0.707 and so x≈ 0.414 — a number strictly between 0 and 1, as every choice is. Second, a rival choice can be tested directly: (C) 1/2 gives r=3/4 and (3/4)¹⁰⁰≈ 3.2 × 10⁻¹³, about 360 times too big, so (C) fails on its own terms. Third, the wrong answers are exactly the near-misses the last line of algebra produces: (E) √(2)/2 is r itself, the value you report if you stop one step early and forget to undo (1+x)/2; (A) 1-√(2)/2 is that same r subtracted in the wrong order; and (D) 2-√(2) is exactly twice (A), the shape you get by doubling at the wrong moment. Only (B) survives all three.

💡Key takeaway

Averaging neighbours in 1,x,x²,… gives back the same kind of list, one term shorter and multiplied by (1+x)/2, so after 100 rounds the only number left is ((1+x)/2)¹⁰⁰ — setting that equal to 1/2⁵⁰ forces 1+x=√(2).

Count the terms and the rounds
Do one round and watch the shape survive
Repeat the same one-line move
Work backwards from the final number
Regroup the exponent, then compare sizes
Keep only the root that positivity allows
Check the candidate end to end