Question

一只蚂蚁在立方体上移动，每一步都沿立方体的一条棱从一个顶点走到相邻顶点。最初蚂蚁在底面的一个顶点，第一步从三个相邻顶点中选一个移动。第一步之后的每一步，蚂蚁都不回到上一个顶点，而是在另外两个相邻顶点中选一个移动。所有选择都是随机的，且每个可能移动等可能。恰好移动 $8$ 步后，蚂蚁位于立方体顶面某个顶点的概率为 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质正整数。求 $m + n$ 。

An ant makes a sequence of moves on a cube where a move consists of walking from one vertex to an adjacent vertex along an edge of the cube. Initially the ant is at a vertex of the bottom face of the cube and chooses one of the three adjacent vertices to move to as its first move. For all moves after the first move, the ant does not return to its previous vertex, but chooses to move to one of the other two adjacent vertices. All choices are selected at random so that each of the possible moves is equally likely. The probability that after exactly $8$ moves that ant is at a vertex of the top face on the cube is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

答案：49

知识点：随机游走递推计数

难度评级：2840

解答：

所有 $3 \cdot 2^7 = 384$ 个允许的移动序列等可能，所以只需数最终在顶面的序列。每步之后按所在面（底面或顶面）以及上一步是否为竖直移动来分类：竖直移动后，在新顶点允许的两个继续方向都是水平棱；水平移动后，一个继续方向是水平棱，另一个是竖直棱。

令 $(B_h, B_v, T_h, T_v)$ 分别表示位于底面或顶面且上一步为水平或竖直移动的序列数。每个序列分成两个后，递推为第 $1$ 步后的计数为 $(2, 0, 0, 1)$ ，继续迭代得到 $(2, 0, 2, 2)$ ， $(2, 2, 6, 2)$ ， $(6, 6, 10, 2)$ ， $(18, 10, 14, 6)$ ， $(38, 14, 26, 18)$ ， $(66, 26, 62, 38)$ ，第八步后 $T_h = 62 + 76 = 138$ ，且 $T_v = 66$ 。 $\begin{aligned} B_h' &= B_h + 2B_v, \\ T_v' &= B_h, \\ T_h' &= T_h + 2T_v, \\ B_v' &= T_h. \end{aligned}$

因此 $384$ 个序列中有 $138 + 66 = 204$ 个最终在顶面，概率为 $\frac{204}{384} = \frac{17}{32}$ ，所以 $m + n = 17 + 32 = 49$ 。

All $3 \cdot 2^7 = 384$ allowed move sequences are equally likely, so we count those ending on the top face. Classify the ant after each move by its face (bottom or top) and by whether its last move was vertical: after a vertical move the two allowed continuations are the two horizontal edges at the new vertex, while after a horizontal move one continuation is horizontal and one is vertical.

Let $(B_h, B_v, T_h, T_v)$ count sequences ending on the bottom or top with last move horizontal or vertical. Each sequence splits into two, following $\begin{aligned} B_h' &= B_h + 2B_v, \\ T_v' &= B_h, \\ T_h' &= T_h + 2T_v, \\ B_v' &= T_h. \end{aligned}$ After move $1$ the counts are $(2, 0, 0, 1),$ and iterating gives $(2, 0, 2, 2),$ $(2, 2, 6, 2),$ $(6, 6, 10, 2),$ $(18, 10, 14, 6),$ $(38, 14, 26, 18),$ $(66, 26, 62, 38),$ and after the eighth move $T_h = 62 + 76 = 138$ and $T_v = 66.$

So $138 + 66 = 204$ of the $384$ sequences end on the top face, giving probability $\frac{204}{384} = \frac{17}{32}$ and $m + n = 17 + 32 = 49.$

2021 AIME II 第 8 题

答案：49

难度评级：2840

解答：

其他年份的第 8 题