Browse · harp
Printsmc
counting and probability senior
Problem
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?
(A)
(B)
(C)
(D)
Solution
Call this cube , with being the starting point. Because in moves the bug has to visit the other vertices, the bug cannot revisit any vertex. Therefore, starting at , the bug has a chance of finding a good path to the next vertex, and call it . Then, the bug has a chance of reaching a new vertex next. Call this . and are always on the same plane. Now, we split cases. Case : The bug goes to the vertex opposite on the space diagonal with probability . Then, the bug has to visit on the plane of last, as there is no way in and out from . Therefore, there is only way out of to get to last. Therefore, there is a chance of finding a good path in this case. Case : The bug goes to vertex on plane with a chance of . The bug then has only way to go to a point on the opposite face, therefore having a probability. Then, the bug has a choice of two vertices on the face opposite to . This results in a probability of finding a good path to a point . Then, there is only way out of to visit both other vertices on that face in moves. Multiply the probabilities for this case to get . Add the probabilities of these two cases together to get
Final answer
C