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

小提示：

虫子必须走出一条访问全部 $8$ 个顶点的路径，也就是 $7$ 条边且没有重复顶点。

The bug must trace a path visiting all $8$ vertices, i.e. $7$ moves with no repeated vertices

大提示：

从起点数这样的路径；所有 $3^7$ 条行走路径等可能。

Count such paths from the start; there are $3^7$ equally likely walks

解答：

经过 $7$ 次移动共有 $3^7 = 2187$ 条等可能路径。成功路径会恰好访问每个顶点一次。

用二进制三元组标记立方体的顶点，使相邻顶点恰好有一个坐标不同。从起点出发，第一步有 $3$ 种选择；若虫子不返回起点，第二步有 $2$ 种选择。由对称性，可将前两步固定为 $000\to100\to110$ 。

成功的后续路线恰好为 $\begin{aligned} 110&\to111\to101\\ &\to001\to011\to010 \end{aligned}\text{、}$ $\begin{aligned} 110&\to010\to011\\ &\to001\to101\to111 \end{aligned}$ 和 $\begin{aligned} 110&\to010\to011\\ &\to111\to101\to001 \end{aligned}\text{。}$ 因此，每一组允许的前两步都有 $3$ 条成功的后续路线，共有 $3\cdot2\cdot3=18$ 条成功路径。

概率为 $\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 题