AMC12 2006 A

AMC12 2006 A · Q20

AMC12 2006 A · Q20. It mainly tests Basic counting (rules of product/sum), Probability (basic).

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) \frac{1}{2187} \frac{1}{2187}

(B) \frac{1}{729} \frac{1}{729}

(D) \frac{1}{81} \frac{1}{81}

(E) \frac{5}{243} \frac{5}{243}

Answer

Correct choice: (C)

正确答案：（C）

Solution

Call this cube $ABCDEFGH$, with $A$ being the starting point. Because in $7$ moves the bug has to visit the other vertices, the bug cannot revisit any vertex. Therefore, starting at $A$, the bug has a $\frac{3}{3}$ chance of finding a good path to the next vertex, and call it $B$. Then, the bug has a $\frac{2}{3}$ chance of reaching a new vertex next. Call this $C$. $A, B,$ and $C$ are always on the same plane. Now, we split cases. Case $1$: The bug goes to the vertex $E$ opposite $A$ on the space diagonal with probability $\frac{1}{3}$. Then, the bug has to visit $D$ on the plane of $ABC$ last, as there is no way in and out from $D$. Therefore, there is only $1$ way out of $81$ to get to $D$ last. Therefore, there is a $\frac{1}{243} \cdot \frac{6}{9} = \frac{6}{2187}$ chance of finding a good path in this case. Case $2$: The bug goes to vertex $D$ on plane $ABC$ with a chance of $\frac{1}{3}$. The bug then has only $1$ way to go to a point $E$ on the opposite face, therefore having a $\frac{1}{3}$ probability. Then, the bug has a choice of two vertices on the face opposite to $ABCD$. This results in a $\frac{2}{3}$ probability of finding a good path to a point $F$. Then, there is only $1$ way out of $9$ to visit both other vertices on that face in $2$ moves. Multiply the probabilities for this case to get $\frac{2}{243} \cdot \frac{6}{9} = \frac{12}{2187}$. Add the probabilities of these two cases together to get $\frac{18}{2187} = \boxed{\textbf{(C) }\frac{2}{243}}.$

将该立方体记为 $ABCDEFGH$，其中 $A$ 为起点。由于在 $7$ 步内虫子必须访问其余顶点，因此虫子不能重复访问任何顶点。因此，从 $A$ 出发，虫子到下一个顶点走出一条“可行路径”的概率为 $\frac{3}{3}$，将该点记为 $B$。接着，虫子以 $\frac{2}{3}$ 的概率到达一个新的顶点，记为 $C$。$A, B, C$ 总在同一平面上。下面分情况讨论。情况 1：虫子以 $\frac{1}{3}$ 的概率走到与 $A$ 通过空间对角线相对的顶点 $E$。此时虫子必须最后访问平面 $ABC$ 上的顶点 $D$，因为从 $D$ 无法既进又出。因此，在 $81$ 种走法中只有 $1$ 种能使 $D$ 最后被访问。所以该情况下找到可行路径的概率为 $\frac{1}{243} \cdot \frac{6}{9} = \frac{6}{2187}$。情况 2：虫子以 $\frac{1}{3}$ 的概率走到平面 $ABC$ 上的顶点 $D$。随后虫子只有 $1$ 种方式走到对面一侧的顶点 $E$，因此该步概率为 $\frac{1}{3}$。接着，虫子在与 $ABCD$ 相对的面上有两个顶点可选。因此以 $\frac{2}{3}$ 的概率找到到达某顶点 $F$ 的可行路径。然后，在接下来的 $2$ 步中访问该面上剩余两个顶点的走法在 $9$ 种中只有 $1$ 种。将该情况的概率相乘得到 $\frac{2}{243} \cdot \frac{6}{9} = \frac{12}{2187}$。将两种情况相加得到 $\frac{18}{2187} = \boxed{\textbf{(C) }\frac{2}{243}}$。

Topics