AMC 10 · 2021 · #18

Grade 9 algebra

Archetype Arithmetic Expression Decomposition └ Sub-archetype Successive Multiplicative Steps

recursive-sequenceexponentspattern-recognitionsequences-geometric pattern-recognitionconvert-to-algebra ↑ Prerequisites: recursive-sequenceexponents

📏 Long solution 💡 4 insights

Problem

A sequence starts at one quarter, and each next term is twice the previous minus twice its square. The terms settle toward one fixed number. Find the smallest index at which a term comes within one over two to the thousandth of that number.

Pick an answer.

(A)

(B)

(C)

123

(D)

329

(E)

401

How to solve

Strategy Change Focus / Count the Complement

The question never asks for u_k itself; it asks how far u_k still is from L. That is the opening for tool #16 (Change Focus): stop tracking the term and start tracking the leftover gap w_k = L - u_k. Tool #5 (Look for a Pattern) supplies the target first — write out four terms, and the gaps come out as 1/4, 1/8, 1/32, 1/512, every one of them a power of 1/2, which says the limit is 1/2 and that powers of 2 are the natural language here. Substituting u_k = 1/2 - w_k collapses the messy quadratic rule into w_k+1 = 2w_k², and then tool #4 (Introduce a Variable) takes one more step down: name the exponent, w_k = 2^-a_k, and even the squaring flattens into the plain rule a_k+1 = 2a_k - 1. Tool #13 (Convert to Algebra) turns the sentence "within 1/2¹⁰⁰⁰" into an inequality between two powers of 2, which is really an inequality between exponents. Tool #14 (Extreme Principle) closes it: the exponents grow, so the condition switches on once and stays on, and the least k is simply the first index that clears the bar.

1STEP 1

Write four terms and watch the gap

Write four terms and watch the gap.

u₀=1/4, u₁=3/8, u₂=15/32, u₃=255/512, with gaps to 1/2 equal to 2⁻², 2⁻³, 2⁻⁵, 2⁻⁹

2STEP 2

Track the gap instead of the term

Track the gap, not the term.

w_k = 1/2-u_k, u_k+1=2u_k(1-u_k)=1/2-2w_k² → w_k+1=2w_k², w₀=1/4

3STEP 3

Name the exponent of the gap

Name the gap's exponent.

w_k = 2^-a_k, a₀=2, w_k+1=2(2^-a_k)² = 2¹-2a_k → a_k+1=2a_k-1

4STEP 4

Solve the exponent rule

Solve the exponent rule.

a_k+1-1 = 2(a_k-1), a₀-1=1 → a_k-1=2^k → a_k = 2^k+1, w_k = 2^-(2^k+1)

5STEP 5

Pin the limit and set up the inequality

Pin the limit and set up the inequality.

L=1/2, |u_k-L| = w_k = 2^-(2^k+1), require 2^-(2^k+1) ≤ 2⁻¹⁰⁰⁰

6STEP 6

Compare exponents and take the least k

Comparing exponents gives 10.

2^-(2^k+1) ≤ 2⁻¹⁰⁰⁰ ⇔ 2^k+1 ≥ 1000 ⇔ 2^k ≥ 999; 2⁹=512 ＜ 999 ≤ 1024=2¹⁰ → k_min=10

Answer

Read the formula |u_k - L| = 2^-(2^k+1) as a statement about binary digits: after k steps the term agrees with 1/2 to about 2^k binary places, so the number of correct digits doubles every step rather than creeping up by a fixed amount. Reaching 1000 digits therefore takes about log₂ 1000 ≈ 10 steps, which is the answer, and the spot check confirms the boundary is sharp: at k=9 the gap is 2⁻⁵¹³, still much larger than 2⁻¹⁰⁰⁰, while at k=10 it is 2⁻¹⁰²⁵, comfortably smaller. The four wrong choices are all in the tens or hundreds, which is what you get from assuming the opposite kind of convergence — that each step buys a fixed number of binary digits. If each step gained roughly 2.5 digits you would land near 401, roughly 3 digits near 329, roughly 8 near 123, roughly 11 near 87. A last check that the algebra is honest: the closed form u_k = 1/2-2^-(2^k+1) gives u₂ = 1/2-1/32 = 15/32 and u₃ = 1/2-1/512 = 255/512, matching the terms computed by hand in step 1.

💡Key takeaway

When a sequence closes in on a limit, follow the leftover distance instead of the terms — the distance usually obeys a much simpler rule, and here it squares itself each step, so the accuracy doubles every time.

Write four terms and watch the gap
Track the gap instead of the term
Name the exponent of the gap
Solve the exponent rule
Pin the limit and set up the inequality
Compare exponents and take the least k