AMC 10 · 2016 · #19

Grade 7 probability

Archetype Branching State Enumeration └ Sub-archetype Constrained Sequence or Path Count

probability-basiclattice-pathsrecursive-sequencecombinations-basic systematic-enumerationidentify-subproblems ↑ Prerequisites: probability-basiccombinations-basic

📏 Long solution 💡 4 insights

Problem

A random walk of fixed length must touch a given position at some moment. Report the reduced probability's parts.

Pick an answer.

(A)

(B)

151

(C)

257

(D)

293

(E)

313

How to solve

Strategy Organize Information in More Ways

The obvious way to organize 256 coin sequences is by where Jerry finishes. That organization is fatally lossy here: "reaches 4" is a fact about the whole journey, not about the finish line, and two sequences with the same finish can disagree about it. Tool #15 (Organize Information in More Ways) fixes exactly that — re-tally the sequences by two pieces of data instead of one, the current position and a flag for whether 4 has already been touched, and no information is lost. Tool #1 (Draw a Diagram) supplies the picture that makes the flag meaningful: the flips trace a walk on the number line, so "touched 4" is a property of the whole track. Tool #7 (Identify Subproblems) splits each new row of the tally into two independent pieces — old successes carried forward, plus brand-new first arrivals. Tool #2 (Make a Systematic List) then just runs the sweep flip by flip, which is pure addition and misses nothing.

1STEP 1

Turn the flips into a walk

Each flip moves the walker one step.

position after t flips = (heads so far) - (tails so far), 2⁸ = 256 equally likely walks

2STEP 2

The finish line is not enough

The finish line alone is not enough.

HHHHTTTT and HTHTHTHT both end at 0, but only the first ever reaches 4

3STEP 3

Sweep the first four flips

Sweeping step by step tracks each position.

t=3: N(-3)=1, N(-1)=3, N(1)=3, N(3)=1, A₃=0 t=4: N(-4)=1, N(-2)=4, N(0)=6, N(2)=4, A₄=1

4STEP 4

Carry successes, add new ones

Successes are carried forward once reached.

A_t+1 = 2A_t + N_t(3) t=5: N(-5)=1, N(-3)=5, N(-1)=10, N(1)=10, N(3)=4, A₅=2 t=6: N(-6)=1, N(-4)=6, N(-2)=15, N(0)=20, N(2)=14, A₆=8

5STEP 5

Finish flips seven and eight

The last steps finish the tally.

t=7: N(-7)=1, N(-5)=7, N(-3)=21, N(-1)=35, N(1)=34, N(3)=14, A₇=16 A₈ = 2 · 16 + 14 = 46

6STEP 6

Divide by all 256 sequences

Dividing by all the walks gives a fraction.

P = A₈/2⁸ = 46/256, 46 + 210 = 256

7STEP 7

Reduce to lowest terms

Reducing gives 151, choice (B).

46/256 = 23/128, gcd(23, 128) = 1, a + b = 23 + 128 = 151 ⟹ (B)

Answer

151

A floor and a spot check both back up 23/128. The floor: any walk that finishes at 4 or higher must have touched 4 on the way, and the finishing counts there are 28 + 8 + 1 = 37 out of 256. So the true probability is at least 37/256 ≈ 0.145, and 23/128 = 46/256 ≈ 0.180 clears that floor by exactly the 9 walks that touch 4 and then come back down below it. That floor also prices out three of the choices, since a probability written over a power of 2 dividing 256 has its numerator and denominator forced: (A) 69 would mean 5/64 = 20/256, (C) 257 would mean 1/256, and (D) 293 would mean 37/256 — the first two sit below the floor, and the third equals the floor exactly, which is impossible because HHHHTTTT touches 4 and finishes at 0. The spot check: among those 9 extra walks, exactly one should finish at 0, since finishing at 0 means four heads and four tails, and touching 4 forces the four heads to come first — so HHHHTTTT and nothing else. The count from the sweep agrees. Finally the total audit already run, 46 + 210 = 256, confirms the tally is complete.

💡Key takeaway

Reaching a number is about the whole journey, not the finish line, so add one yes-or-no column to your table for "already got there" and sweep it forward one flip at a time.

Turn the flips into a walk
The finish line is not enough
Sweep the first four flips
Carry successes, add new ones
Finish flips seven and eight
Divide by all 256 sequences
Reduce to lowest terms