Question

一只虫子从立方体的一个顶点出发，并按照以下规则沿立方体的边移动。在每个顶点，虫子会从该顶点发出的三条边中选择一条走。每条边被选中的概率相等，且所有选择相互独立。经过七次移动后，虫子恰好访问每个顶点一次的概率是多少？

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?

$\dfrac{1}{2187}$

$\dfrac{1}{729}$

$\dfrac{2}{243}$

$\dfrac{1}{81}$

$\dfrac{5}{243}$

答案：C

知识点：图论基本概率分类讨论

难度评级：2120

解答：

经过 $7$ 次移动共有 $3^7 = 2187$ 条等可能路径。

成功路径必须恰好访问每个顶点一次。从起点出发，第一步有 $3$ 种选择，第二步有 $2$ 种选择（不能返回）。 $000\to100\to110$ 。

将前三个顶点标为 $3$ 后，虫子必须走向两个顶点之一，之后路线除了一个二选一之外被迫确定，因此共有 $3\cdot2\cdot3=18$ 条这样的路径。 $\begin{aligned} 110&\to111\to101\\ &\to001\to011\to010, \end{aligned}$ $\begin{aligned} 110&\to010\to011\\ &\to001\to101\to111, \end{aligned}$ $\begin{aligned} 110&\to010\to011\\ &\to111\to101\to001. \end{aligned}$

概率为 $\frac{18}{2187} = \frac{2}{243}$ 。

所以正确答案是 C。

After $7$ moves there are $3^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 $3$ choices for the first move and $2$ for the second move if the bug is not to return to its starting point. By symmetry, fix these first moves as $000\to100\to110.$

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

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

Thus, the correct answer is C.

2006 AMC 10A 第 25 题

答案：C

难度评级：2120

解答：

其他年份的第 25 题