AMC10 2006 A

AMC10 2006 A · Q25

AMC10 2006 A · Q25. 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) $\dfrac{1}{2187}$ $\dfrac{1}{2187}$

(B) $\dfrac{1}{729}$ $\dfrac{1}{729}$

(D) $\dfrac{1}{81}$ $\dfrac{1}{81}$

(E) $\dfrac{5}{243}$ $\dfrac{5}{243}$

Answer

Correct choice: (C)

正确答案：（C）

Solution

(C) At each vertex there are three possible locations that the bug can travel to in the next move, so the probability that the bug will visit three different vertices after two moves is $2/3$. Label the first three vertices that the bug visits as $A$ to $B$ to $C$, as shown in the diagram. In order to visit every vertex, the bug must travel from $C$ to either $G$ or $D$. The bug travels to $G$ with probability $1/3$, and from there the bug must visit the vertices $F$, $E$, $H$, $D$ in that order. Each of these choices has probability $1/3$ of occurring. So the probability that the path continues in the form $$ C \to G \to F \to E \to H \to D $$ is $\left(\frac{1}{3}\right)^5$. Alternatively, the bug could travel from $C$ to $D$ with probability $1/3$, and then travel to $H$, which also occurs with probability $1/3$. From $H$ the bug could go either to $G$ or $E$, with probability $2/3$, and from there to the two remaining vertices, each with probability $1/3$. So the probability that the path continues in one of the forms $$ \begin{array}{c} C \to D \to H \to E \to F \to G \\ C \to D \to H \to G \to F \to E \end{array} $$ is $\left(\frac{2}{3}\right)\left(\frac{1}{3}\right)^4$. Hence the bug will visit every vertex in seven moves with probability $$ \left(\frac{2}{3}\right)\left[\left(\frac{1}{3}\right)^5+\left(\frac{2}{3}\right)\left(\frac{1}{3}\right)^4\right] =\left(\frac{2}{3}\right)\left(\frac{1}{3}+\frac{2}{3}\right)\left(\frac{1}{3}\right)^4 =\frac{2}{243}. $$

（C）在每个顶点，甲虫下一步有三个可能到达的位置，因此甲虫在走两步后访问到三个不同顶点的概率为 $2/3$。把甲虫最先访问的三个顶点标记为 $A \to B \to C$，如图所示。为了访问到每一个顶点，甲虫必须从 $C$ 走到 $G$ 或 $D$。甲虫以概率 $1/3$ 走到 $G$，并且从那里起必须按顺序访问顶点 $F、E、H、D$。这些选择中每一次发生的概率都是 $1/3$。因此路径按如下形式继续的概率 $$ C \to G \to F \to E \to H \to D $$ 为 $\left(\frac{1}{3}\right)^5$。或者，甲虫也可能以概率 $1/3$ 从 $C$ 走到 $D$，然后再以概率 $1/3$ 走到 $H$。从 $H$ 出发，甲虫可以以概率 $2/3$ 走到 $G$ 或 $E$，并从那里再走到剩下的两个顶点（每次概率均为 $1/3$）。因此路径按下列两种形式之一继续的概率 $$ \begin{array}{c} C \to D \to H \to E \to F \to G \\ C \to D \to H \to G \to F \to E \end{array} $$ 为 $\left(\frac{2}{3}\right)\left(\frac{1}{3}\right)^4$。因此，甲虫用 7 步访问到所有顶点的概率为 $$ \left(\frac{2}{3}\right)\left[\left(\frac{1}{3}\right)^5+\left(\frac{2}{3}\right)\left(\frac{1}{3}\right)^4\right] =\left(\frac{2}{3}\right)\left(\frac{1}{3}+\frac{2}{3}\right)\left(\frac{1}{3}\right)^4 =\frac{2}{243}. $$

Topics