AMC 10 · 2021 · #17

Grade 8 probability

Archetype Branching State Enumeration └ Sub-archetype Markov State Probability

recursive-sequenceprobability-basicsymmetry-argumentfundamental-counting-principle identify-subproblemssymmetry-argument ↑ Prerequisites: probability-basicrecursive-sequence

📏 Long solution 💡 4 insights

Problem

A bug sits on a point of a grid built from unit equilateral triangles. Six grid lines leave every point, and at each step the bug picks one at random, all equally likely and independent, then walks one unit. The bug takes five steps. Find the probability that its distance from the start stays at most one after every step.

Pick an answer.

(A)

$\frac{13}{108}$

(B)

$\frac{7}{54}$

(C)

$\frac{29}{216}$

(D)

$\frac{4}{27}$

(E)

$\frac{1}{16}$

How to solve

Strategy Organize Information in More Ways

Listing 6⁵ = 7776 direction sequences is out of the question, and tracking the bug's exact position is barely better. The saving observation is that only seven grid points are ever legal: the start and the six points at distance 1. Those six ring points are interchangeable under rotation, so the bug's exact position never matters, only whether it is at the centre or on the ring. Collapsing seven positions into two states turns the walk into a two-number update rule that can be run by hand five times. The counting version gives the numerator directly; running the same rule a second time with fractions instead of tallies is an independent check that has to agree.

1STEP 1

Map the safe zone

Map the safe zone.

safe set = {O} ∪ {the 6 grid points at distance 1 from O}

2STEP 2

Count the safe moves from each spot

Count the safe moves from each spot.

√((3/2)² + (√(3)/2)²) = √(9/4 + 3/4) = √(3) ＞ 1

3STEP 3

Collapse seven points into two states

Collapse seven points into two states.

c_n+1 = r_n, r_n+1 = 6c_n + 2r_n, c₀ = 1, r₀ = 0

4STEP 4

Run the table out to five steps

Run the table out to five steps.

(c₁, r₁) = (0, 6), (c₂, r₂) = (6, 12), (c₃, r₃) = (12, 60), (c₄, r₄) = (60, 192), (c₅, r₅) = (192, 744) → c₅ + r₅ = 936

5STEP 5

Turn the count into a probability

Turn the count into a probability.

936/7776 = 117/972 = 13/108

6STEP 6

Re-run the walk with fractions

Re-running with fractions confirms thirteen over one hundred eight.

u_n+1 = 1/6v_n, v_n+1 = u_n + 1/3v_n → u₅ + v₅ = 2/81 + 31/324 = 39/324 = 13/108

Answer

13/108

The value 13/108 is about 0.120, and a rough estimate confirms that size. The first move is always safe, so the question is really about the last four moves. If the bug were stuck on the ring for all of them, each would be safe with probability 1/2, giving (1/2)⁴ = 1/16 — which is exactly choice (E). The true answer has to be larger, because every time the bug steps back to the centre it earns a move that is safe with probability 1 instead of 1/2, and 0.120 is a little under twice 0.0625. So (E) is the trap for anyone who forgets that returning to the centre is possible. Two further checks: the count 936 must be a multiple of 6, since rotating the whole picture by 60 degrees permutes the safe paths, and indeed 936 = 6 · 156; and the reduced denominator 108 must divide 6⁵ = 7776, which it does, since 7776 = 108 · 72.

💡Key takeaway

Only seven spots are ever legal, and the six outer ones all behave the same, so track just "centre or ring": the centre offers 6 safe moves and a ring spot offers 3, and five rounds of that bookkeeping cut 7776 paths down to 936.

Map the safe zone
Count the safe moves from each spot
Collapse seven points into two states
Run the table out to five steps
Turn the count into a probability
Re-run the walk with fractions