AMC 10 · 2023 · #17

Grade 11 probability

Archetype Branching State Enumeration └ Sub-archetype Markov State Probability

probability-basicgeometric-series-infinitestars-and-barsrecursive-sequence easier-related-problempattern-recognitionidentify-subproblems ↑ Prerequisites: probability-basicgeometric-series-infinite

📏 Long solution 💡 3 insights

Problem

A frog starts at zero on the number line and hops only to the right. Each hop is a whole number of units, a hop of length m happening with probability two to the minus m, independently. It hops forever. Since it never turns around, it either lands exactly on ten or jumps clean over it. Find the probability that it lands exactly on ten.

Pick an answer.

(A)

$\frac{5}{512}$

(B)

$\frac{45}{1024}$

(C)

$\frac{127}{1024}$

(D)

$\frac{511}{1024}$

(E)

$\frac{1}{2}$

How to solve

Strategy Make a Systematic List

At first sight this looks like an infinite probability calculation: there are trips of one hop, trips of two hops, all the way up to trips of ten hops, and each seems to need its own weight. Tool #15 (Organize Information in More Ways) removes that fear in a single line. Rewrite the probability of a whole trip as one power of 2 instead of a product of many, and the exponents add to the distance travelled — so every trip that reaches 10 is worth exactly the same amount, no matter how many hops it used. Once all the weights are equal, the probability question has quietly turned into a counting question, and that is where tool #2 (Make a Systematic List) takes over as the main engine: count the ordered ways to write 10 as a sum of positive integers, which is a clean yes-or-no choice at each of the nine gaps between the ten unit steps. Tool #4 (Introduce a Variable) is what makes the ending elegant rather than lucky — replace the target 10 by a general n and the count becomes 2^ n-1 against a weight of 1/2ⁿ, so the n cancels and the answer is the same for every target. Tool #7 (Identify Subproblems) supplies a second, completely independent confirmation by conditioning on the first hop, which turns the problem into a smaller copy of itself and gives a recursion that can be settled by induction — a proof for all n, not a guess from small cases. Tool #5 (Look for a Pattern) does the housekeeping first: the running totals of the hop probabilities reveal the geometric series that confirms this is a legal probability rule at all.

1STEP 1

Check the hop rule

The probabilities sum to one.

Σ_m=1^M1/2^m = 1-1/2^M ⟹ Σ_m=1^∞1/2^m = 1/2/(1-1/2) = 1

2STEP 2

Ask about every target at once

Ask about every target at once.

p_n = P(the frog's position equals n at some moment), p₀=1, goal: p₁₀

3STEP 3

Price one route

Every route has the same probability.

P(m₁,m₂,…,m_k) = 1/2^m₁·1/2^m₂…1/2^m_k = 1/(2^ m₁+m₂+…+m_k) = 1/2ⁿ

4STEP 4

Count the routes

Count by breaking the gaps.

number of trips reaching n = 2^ n-1; n=10 ⟹ 2⁹ = 512

5STEP 5

Multiply count by price

Multiplying gives a target-independent value.

p_n = 2^ n-1·1/2ⁿ = (2^ n-1)/2ⁿ = 1/2; p₁₀ = 512·1/1024 = 512/1024 = 1/2

6STEP 6

Confirm with a recursion

A recursion confirms one half.

p_n = 1/2ⁿ · 1 + Σ_m=1ⁿ⁻¹1/2^m·1/2 = 1/2ⁿ + 1/2(1-1/(2^ n-1)) = 1/2ⁿ + 1/2 - 1/2ⁿ = 1/2 (E)

Answer

1/2

First the crude checks: 1/2 sits between 0 and 1, and it should not be close to either end — the frog has 512 separate ways to hit 10, so success cannot be rare, yet a single careless leap of 11 or more ends the matter, so success cannot be near certain. Next, run the recursion p_n = Σ_m=1ⁿ1/2^mp_n-m from p₀=1 as exact fractions and read off the values: p₁=p₂=p₃=…=p₁₂=1/2, every one of them, with no drift. Independently, brute-force enumeration of the trips agrees at every size: n has 2^ n-1 trips (1, 2, 4, 8, …, 512 for n=1 through 10) and their probabilities sum to 1/2 each time. The two computations use different logic and land on the same number. Finally, the distractors are worth naming. Choice (D) 511/1024 is the near miss: it is 512/1024 short by exactly one trip, which is what an off-by-one in the gap count produces — counting 2⁹-1 break patterns by forgetting that 'no breaks at all' is the legitimate single hop (10). Since 512/1024 reduces to the tidy 1/2, the two choices differ by only 1/1024, so the count must be exactly right, not nearly right. Choice (C) 127/1024 is (2⁷-1)/2¹⁰, another gap-counting slip, while (A) and (B) are far too small for 512 equally likely successful trips.

💡Key takeaway

Every possible route to 10 costs exactly the same, 1/1024, so the probability question turns into a counting question — and there are 512 routes, which is exactly half of 1024.

Check the hop rule totals 1
Ask about every target at once
Price one trip to the target
Count the trips by breaking gaps
Multiply the count by the price
Confirm with a first-hop recursion