2006 AMC 10A Problem 25

Attempt Problem 25 of the 2006 AMC 10A below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2006 AMC 10A solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

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?

12187\dfrac{1}{2187}

1729\dfrac{1}{729}

2243\dfrac{2}{243}

181\dfrac{1}{81}

5243\dfrac{5}{243}

Answer: C
Concepts:graph theorybasic probabilitycasework
Difficulty rating: 2120
Solution:

After 77 moves there are 37=21873^7 = 2187 equally likely walks. A successful walk visits every vertex exactly once.

Label the cube's vertices by binary triples, with adjacent vertices differing in one coordinate. There are 33 choices for the first move and 22 for the second move if the bug is not to return to its starting point. By symmetry, fix these first moves as 000100110.000\to100\to110.

The successful continuations are exactly 110111101001011010, \begin{aligned} 110&\to111\to101\\ &\to001\to011\to010, \end{aligned} 110010011001101111, \begin{aligned} 110&\to010\to011\\ &\to001\to101\to111, \end{aligned} and 110010011111101001. \begin{aligned} 110&\to010\to011\\ &\to111\to101\to001. \end{aligned} Thus each allowed pair of first moves has 33 successful continuations, giving 323=183\cdot2\cdot3=18 successful walks.

The probability is 182187=2243.\frac{18}{2187} = \frac{2}{243}.

Thus, the correct answer is C.

← Problem 24#24
Full Exam

Problem 25 in Other Years