2006 AMC 12A 第 20 题

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

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

难度评级：2070

小提示：

3^7

条等可能的

7

-步路径；数出访问全部

8

个顶点的路径。

There are

3^7

equally likely

7

-move walks; count those visiting all

8

vertices

大提示：

第一步有

3

种选择，第二步有

2

种选择，之后路径几乎被确定。

There are

3

choices for the first move and

2

for the second, after which the path is nearly forced

解答：

从起点出发共有

3^7

条等可能的

7

-步路径。考虑一条访问全部

8

个顶点的路径：第一步有

3

种选择，第二步有

2

种选择。

用三位二进制串给立方体的顶点编号。由对称性，固定前两步之后，可设前三个顶点依次为

000,001,011

。逐个分支检验可知，恰好只有以下三种走完全程的方式：

\begin{aligned} &010,110,111,101,100,\\ &010,110,100,101,111,\\ &111,101,100,110,010 \end{aligned}\text{。}

因此这样的路径共有

3 \cdot 2 \cdot 3 = 18

条。

概率为

\dfrac{18}{3^7} = \dfrac{18}{2187} = \dfrac{2}{243}

。

因此，正确答案是 C。

From the start there are

3^7

equally likely

7

-move walks. For a walk visiting all

8

vertices, there are

3

choices for the first move and

2

for the second, since it cannot return to the starting vertex.

Label cube vertices by three-bit strings. By symmetry, after fixing those first two moves we may take the first three vertices to be

000,001,011.

A branch check gives exactly these three completions:

\begin{aligned} &010,110,111,101,100,\\ &010,110,100,101,111,\\ &111,101,100,110,010. \end{aligned}

Thus there are

3 \cdot 2 \cdot 3 = 18

such walks.

The probability is

\dfrac{18}{3^7} = \dfrac{18}{2187} = \dfrac{2}{243}.

Thus, the correct answer is C.

2006 AMC 12A 第 20 题

答案：C

难度评级：2070

小提示：

大提示：

解答：

其他年份的第 20 题