2006 AMC 10A Problem 25

P21-25~8 minPrint

Basic Probability Paths & Grids Split into exhaustive cases and handle each Exploit symmetry to reduce work or pair up objects

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?

Show solution without answering

Key insight

By symmetry fix the first two moves (3 × 2 ways). Only 3 ways to finish visit every corner: 18 good paths out of 3^7 = 2187.

Solution

Seven moves visit $8$ corners (counting the start), and a cube has exactly $8$ corners. So the bug must never return to a corner it has already visited.

1. All sequences. At each move the bug has $3$ equal choices, so there are $3^7 = 2187$ equally likely sequences. We count the good ones.
2. Label the cube. Top face $A, B, C, D$ going around; bottom face $E, F, G, H$ with $E$ under $A$ , $F$ under $B$ , $G$ under $C$ , $H$ under $D$ . The bug starts at $A$ .
3. First two moves. The first move has $3$ choices and the second has $2$ (it cannot go back). All $3 \times 2 = 6$ starts look the same after turning the cube, so count the good paths for one start, $A \to B \to C$ , and multiply by $6$ .
4. From $C$ , the unvisited neighbors are $D$ and $G$ .
- Go to $D$ . From $D$ the only new neighbor is $H$ . From $H$ , walk around the bottom face either way: $H \to G \to F \to E$ or $H \to E \to F \to G$ . That is $2$ good paths.
- Go to $G$ , then $F$ . From $F$ the only new neighbor is $E$ ( $B$ is used). Then $E \to H \to D$ . That is $1$ good path.
- Go to $G$ , then $H$ . Left unvisited: $D$ , $E$ , $F$ . Going to $D$ is a dead end (its neighbors $A$ , $C$ , $H$ are used). Going to $E$ then $F$ leaves $D$ unreachable. That is $0$ good paths.
5. Total. $3$ good paths for this start, so $6 \times 3 = 18$ in all. The probability is
$\frac{18}{2187} = \frac{2}{243}.$

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

Why this works

When every step is an equal random choice, probability is (good sequences) divided by (all sequences), so the job is counting. Symmetry lets you fix the first few moves and multiply at the end, and after that the cube is small enough to list the cases, stopping each branch as soon as some corner can no longer be reached.

Alternative approach

Check the choices. The first two moves can always be anything ( $3 \times 2 = 6$ ways), and each start has the same number of good endings, so the number of good paths is a multiple of $6$ . The choices, written over $2187$ , are $\frac{1}{2187}$ , $\frac{3}{2187}$ , $\frac{18}{2187}$ , $\frac{27}{2187}$ and $\frac{45}{2187}$ . Only $18$ is a multiple of $6$ , so the answer is (C).

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

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

Label the top face $ABCD$ in order and the bottom face $EFGH$ with $E$ below $A$ , $F$ below $B$ , $G$ below $C$ , $H$ below $D$ . Start at $A$ . The first move has $3$ options and the second has $2$ (no going back); by symmetry every such start is equivalent, so assume the path begins $A \to B \to C$ and multiply by $6$ later.

From $C$ the unvisited neighbors are $D$ and $G$ .

Case 1: $C \to D$ . From $D$ the only unvisited neighbor is $H$ . From $H$ the rest of the bottom face is traversed either way: $H \to G \to F \to E$ or $H \to E \to F \to G$ . That is $2$ paths.

Case 2: $C \to G$ . From $G$ , go to $F$ or $H$ .
- $G \to F$ : then $F \to E$ (since $B$ is used), $E \to H$ , $H \to D$ . $1$ path.
- $G \to H$ : the unvisited vertices are $D, E, F$ . Going to $D$ strands $E$ and $F$ ; going to $E$ then $F$ strands $D$ . $0$ paths.

So $3$ completions follow $A \to B \to C$ , and there are $6 \cdot 3 = 18$ good sequences in all. The probability is
$\frac{18}{2187} = \frac{2}{243}.$

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

Review in the AoPS books

Introduction to Counting & Probability, Chapter 7: Introduction to Probability
Introduction to Counting & Probability, Chapter 5: More With Combinations (§5.2)
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.2)
Introduction to Algebra, Chapter 22: Special Manipulations (§22.3)