AMC 10 Step by Step
Log inSign up
Printable

2006 AMC 10A Problem 25

Problem onlyBack to the problem
2006 AMC 10A Problem 25AMC 10 Step by Step
Name:                             Date: September 13, 2026
Basic Probability · difficulty 5 of 5 · about 8 min · position P21-25

A bug starts at one vertex of a cube and moves along the edges of the cube according to the following rule. At each vertex the bug will choose to travel along one of the three edges emanating from that vertex. Each edge has equal probability of being chosen, and all choices are independent. What is the probability that after seven moves the bug will have visited every vertex exactly once?

  1. A)

    12187\frac{1}{2187}

  2. B)

    1729\frac{1}{729}

  3. C)

    2243\frac{2}{243}

  4. D)

    181\frac{1}{81}

  5. E)

    5243\frac{5}{243}

Answer

C

Key insight

Fix the first two moves by symmetry (3 · 2 ways); only 3 of the remaining continuations visit every vertex, so 18 good paths out of 3^7 equally likely ones.

Solution

Seven moves reach eight vertices, so the walk must never repeat a vertex. All 37=21873^7 = 2187 move sequences are equally likely, so we count the non-repeating ones.

Label the top face ABCDABCD in order and the bottom face EFGHEFGH with EE below AA, FF below BB, GG below CC, HH below DD. Start at AA. The first move has 33 options and the second has 22 (no going back); by symmetry every such start is equivalent, so assume the path begins A→B→CA \to B \to C and multiply by 66 later.

From CC the unvisited neighbors are DD and GG.

Case 1: C→DC \to D. From DD the only unvisited neighbor is HH. From HH the rest of the bottom face is traversed either way: H→G→F→EH \to G \to F \to E or H→E→F→GH \to E \to F \to G. That is 22 paths.

Case 2: C→GC \to G. From GG, go to FF or HH.
- G→FG \to F: then F→EF \to E (since BB is used), E→HE \to H, H→DH \to D. 11 path.
- G→HG \to H: the unvisited vertices are D,E,FD, E, F. Going to DD strands EE and FF; going to EE then FF strands DD. 00 paths.

So 33 completions follow A→B→CA \to B \to C, and there are 6⋅3=186 \cdot 3 = 18 good sequences in all. The probability is
182187=2243.\frac{18}{2187} = \frac{2}{243}.

The answer is (C) 2243\boxed{\textbf{(C)}\ \frac{2}{243}}.

Why this works

With a uniform choice at every step, the probability is (good sequences)/(all sequences), so the problem is really counting Hamiltonian paths from a vertex of the cube. Symmetry collapses the first two moves to a single representative, and after that the cube is small enough that a short case tree, pruned whenever a vertex becomes unreachable, finishes the count.

Alternative approach

Answer-choice check: the first two moves are always free (3⋅23 \cdot 2 ways) and the rest is determined by symmetry, so the number of good paths is a multiple of 66 and the probability has the form 6k2187\tfrac{6k}{2187}. Only 2243=182187\tfrac{2}{243} = \tfrac{18}{2187} fits; the others are 12187,32187,272187,452187\tfrac{1}{2187}, \tfrac{3}{2187}, \tfrac{27}{2187}, \tfrac{45}{2187}.

The trap

Forgetting to multiply the 3 completions by the 3 · 2 choices for the first two moves (giving 3/2187 = 1/729, choice (B)), or using 3^8 as the total.

Common mistakes

  • Forgetting to multiply the 33 completions by the 3⋅23 \cdot 2 choices for the first two moves (giving 32187=1729\tfrac{3}{2187} = \tfrac{1}{729}, choice (B)), or using 383^8 as the total.
  • Overlooking that a Hamiltonian path may never return to the start, so counting closed circuits or allowing the seventh move to revisit AA.

Techniques

Split into exhaustive cases and handle each · Exploit symmetry to reduce work or pair up objects