AMC 10 · 2005 · #20

Grade 9 algebracounting

Archetype Branching State Enumeration └ Sub-archetype Numeric Operation Tree

function-compositionrecursive-sequenceexponents work-backwardseasier-related-problempattern-recognition ↑ Prerequisites: function-compositionfunction-evaluationexponents

📏 Long solution 💡 3 insights

Problem

A function folds an interval onto itself, doubling on the left half and doubling the distance from the right end on the other. It is applied 2005 times in a row. Count the starting values that end at the midpoint.

Pick an answer.

(A)

(B)

2005

(C)

4010

(D)

$2005^2$

(E)

$2^{2005}$

How to solve

Strategy Work Backwards

Running f forward 2005 times is hopeless, but the finish line is known exactly. Asking what could have produced 1/2 one step earlier turns the problem into repeated preimage counting, and the count for one backward step is the same at every stage. Small cases (n=1, n=2) reveal that constant, and the tent-shaped graph of f explains why it is what it is.

1STEP 1

Check the outputs stay inside

The rule sends the interval into itself, so every repetition is defined.

f([0,1]) = [0,1]

2STEP 2

Turn the target into a preimage

Working backwards turns the question into a chain of preimages.

S_n+1 = { x ∈ [0,1] : f(x) ∈ S_n }

3STEP 3

Two sources for each interior value

Each interior value has exactly two sources, one per branch.

f(x) = y ⇔ x = y/2 or x = 1 - y/2, 0 ＜ y ＜ 1

4STEP 4

Do the first two steps by hand

The first two rounds give 2 then 4 values.

S₁ = { 1/4, 3/4 }, S₂ = { 1/8, 3/8, 5/8, 7/8 }

5STEP 5

Prove the doubling never breaks

Induction shows every value stays strictly inside, so doubling never breaks.

|S_n+1| = 2 |S_n| for every n ≥ 1

6STEP 6

Multiply the doublings

Multiplying the doublings gives 2²⁰⁰⁵, choice (E).

|S_n| = 2 · 2^ n-1 = 2ⁿ → |S₂₀₀₅| = 2²⁰⁰⁵

Answer

2²⁰⁰⁵

Three of the choices — 2005, 4010, and 2005² — grow like a polynomial in the number of iterations, but each backward step multiplies the count by 2, so the growth has to be exponential. Choice (A) is out immediately because x = 1/4 already works for one iteration. The formula |S_n| = 2ⁿ also matches the two cases computed by hand, |S₁| = 2 and |S₂| = 4, and the listed solutions are exactly the odd numerators over 2ⁿ⁺¹, none of which is 0 or 1.

💡Key takeaway

If every step backwards has exactly two possible starting points, then 2005 steps backwards has 2²⁰⁰⁵ of them.

Check the outputs stay inside
Turn the target into a preimage
Two sources for each interior value
Do the first two steps by hand
Prove the doubling never breaks
Multiply the doublings