AMC 10 · 2006 · #25
Grade 7 geometry-3dA 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?
Pick an answer.
AMC 10 2006 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: A bug sits on a corner of a cube. It makes $7$ moves; each move it slides along one of the $3$ edges leaving its current corner, picking each edge with equal chance and independently of past moves. Find the probability that these $7$ moves carry the bug through all $8$ corners, hitting each corner exactly once.
Givens: The bug starts at one fixed vertex of a cube.; Each vertex has exactly $3$ edges leaving it.; At every vertex all $3$ edges are equally likely ($\tfrac{1}{3}$ each) and choices are independent.; The bug makes exactly $7$ moves.; Success means every one of the $8$ vertices is visited exactly once.; Answer choices: (A) $\tfrac{1}{2187}$, (B) $\tfrac{1}{729}$, (C) $\tfrac{2}{243}$, (D) $\tfrac{1}{81}$, (E) $\tfrac{5}{243}$.
Unknowns: The probability that the $7$-move walk visits all $8$ vertices exactly once.
Understand
Restated: A bug sits on a corner of a cube. It makes $7$ moves; each move it slides along one of the $3$ edges leaving its current corner, picking each edge with equal chance and independently of past moves. Find the probability that these $7$ moves carry the bug through all $8$ corners, hitting each corner exactly once.
Givens: The bug starts at one fixed vertex of a cube.; Each vertex has exactly $3$ edges leaving it.; At every vertex all $3$ edges are equally likely ($\tfrac{1}{3}$ each) and choices are independent.; The bug makes exactly $7$ moves.; Success means every one of the $8$ vertices is visited exactly once.; Answer choices: (A) $\tfrac{1}{2187}$, (B) $\tfrac{1}{729}$, (C) $\tfrac{2}{243}$, (D) $\tfrac{1}{81}$, (E) $\tfrac{5}{243}$.
Plan
Primary tool: #2 Make a Systematic List
Secondary: #1 Draw a Diagram, #17 Visualize Spatial Relationships, #7 Identify Subproblems
Because every $7$-move sequence is equally likely, the probability is just (number of successful walks) divided by (number of all walks) — that is the subproblem split (Tool #7). Counting all walks is easy: $3$ choices per move. The hard half is counting the successful walks, which are exactly the routes that touch all $8$ corners without repeating one. To count those cleanly you must name the corners, so draw and label the cube (Tool #1) and hold its shape in mind (Tool #17). Then walk through the possibilities in an orderly way (Tool #2, the 'how many ways' tool): fix the first move by symmetry, and follow the forced branches until every good route is listed. A systematic list is the right instrument because the successful routes are few and highly constrained — most partial walks paint themselves into a corner.
Execute — Answer: C
7.SP.C.7 Step 1 Turn probability into a count of routes
- Every move picks $1$ of $3$ equally likely edges, so each specific $7$-move sequence has the same probability.
- That means the probability of success equals the number of successful $7$-move routes divided by the number of all $7$-move routes.
- So the whole problem becomes two counting problems: count all routes, then count the good ones.
💡 When every outcome is equally likely, probability is just a fraction of favorable cases over total cases.
6.EE.A.1 Step 2 Count all possible routes
- At each of the $7$ moves the bug has $3$ edges to choose from, and the choices are independent.
- Multiplying the choices gives $3 \times 3 \times 3 \times 3 \times 3 \times 3 \times 3 = 3^7 = 2187$ possible routes.
- This is the denominator.
💡 Independent choices multiply, so $7$ moves with $3$ options each give $3^7$ routes.
7.SP.C.8 Step 3 Label the cube and pin down the first move
- Name the bottom corners $A, B, C, D$ going around the square, and the top corners $E, F, G, H$ sitting directly above $A, B, C, D$.
- Edges run around the bottom ($A\!-\!B\!-\!C\!-\!D\!-\!A$), around the top ($E\!-\!F\!-\!G\!-\!H\!-\!E$), and up the four posts ($A\!-\!E$, $B\!-\!F$, $C\!-\!G$, $D\!-\!H$).
- Let the bug start at $A$.
- Its first move goes to $B$, $D$, or $E$.
- These three look identical by the cube's symmetry, so count the good routes that begin $A\to B$ and multiply by $3$ at the end.
💡 Symmetry lets you solve one representative case and scale up, instead of redoing identical work.
7.SP.C.8 Step 4 List every good route after A to B
- From $B$ the unused edges go to $C$ or $F$; by symmetry these two also match, so each leads to the same number of good routes — find them for $B\to C$.
- After $A\to B\to C$, the bug must next take $C\to D$ or $C\to G$.
- Following the forced choices (never repeat a corner, and never trap yourself away from an unvisited corner) gives exactly three good routes: $A\,B\,C\,D\,H\,E\,F\,G$, $A\,B\,C\,D\,H\,G\,F\,E$, and $A\,B\,C\,G\,F\,E\,H\,D$.
- Any other continuation strands an unreachable corner.
- So $A\to B\to C$ yields $3$ good routes, and by symmetry $A\to B\to F$ yields $3$ more, giving $6$ good routes that start $A\to B$.
💡 Once two moves are fixed, the 'visit all, repeat none' rule forces the rest, so only a handful of routes survive.
4.OA.A.3 Step 5 Total the good routes and form the probability
- Each of the $3$ symmetric first moves gives $6$ good routes, so there are $3 \times 6 = 18$ successful routes in all.
- The probability is therefore $\tfrac{18}{2187}$.
- Simplify by dividing top and bottom by $9$: $\tfrac{18}{2187} = \tfrac{2}{243}$.
- That is choice (C).
💡 Good routes over all routes, reduced to lowest terms, is the answer.
7.SP.C.7 Every move picks $1$ of $3$ equally likely edges, so each specific $7$-move sequ 6.EE.A.1 At each of the $7$ moves the bug has $3$ edges to choose from, and the choices a 7.SP.C.8 Name the bottom corners $A, B, C, D$ going around the square, and the top corner 7.SP.C.8 From $B$ the unused edges go to $C$ or $F$; by symmetry these two also match, so 4.OA.A.3 Each of the $3$ symmetric first moves gives $6$ good routes, so there are $3 \ti Review
Reasonableness: The count $18$ is believable: a successful route is a Hamiltonian path of the cube from a fixed start, and the cube is symmetric enough that these come in a small, tidy number. A quick sanity check on the size — $\tfrac{18}{2187}$ is a bit under $1\%$, which fits: touching all $8$ corners in exactly $7$ non-repeating moves is a demanding, rare event, so a probability near a hundredth is sensible. The value also lands exactly on an answer choice, $\tfrac{2}{243}$, and no arithmetic was fudged to get there: $2187 = 3^7$ and $18/9 = 2$, $2187/9 = 243$.
Alternative: Instead of listing routes, reason with probabilities move by move for the $A\to B\to C$ representative. From the start the bug has probability $1$ of stepping to a new corner, then $\tfrac{2}{3}$ of stepping to a second new corner, and so on; carefully tracking the fraction of choices that keep the 'visit-all-once' hope alive and summing the two structural cases (crossing to the far corner early vs. finishing a face first) reproduces $\tfrac{2}{243}$. This confirms the answer without an explicit route list, though the systematic list is easier to trust because you can see every good route written out.
CCSS standards used (min grade 7)
7.SP.C.7Develop a uniform probability model and use it to find probabilities of events (Recognizing that all $3^7$ move sequences are equally likely, so the probability is (good routes)/(all routes).)6.EE.A.1Write and evaluate numerical expressions involving whole-number exponents (Computing the total number of routes as $3^7 = 2187$.)7.SP.C.8Find probabilities of compound events using organized lists, tables, tree diagrams, and simulation (Enumerating the successful routes with a symmetry-reduced organized list on the labeled cube.)4.OA.A.3Solve multistep word problems using the four operations (Combining $3 \times 6 = 18$ good routes and simplifying $\tfrac{18}{2187} = \tfrac{2}{243}$.)
⭐ Every $7$-move path is equally likely, so the answer is just (paths that hit all $8$ corners once) over (all $3^7 = 2187$ paths); careful listing shows only $18$ good paths, giving $\tfrac{18}{2187} = \tfrac{2}{243}$.
⭐ Every $7$-move path is equally likely, so the answer is just (paths that hit all $8$ corners once) over (all $3^7 = 2187$ paths); careful listing shows only $18$ good paths, giving $\tfrac{18}{2187} = \tfrac{2}{243}$.
More like this
Same archetype — closest grade level first.