Question

设 $A_1A_2A_3 \ldots A_{12}$ 是一个 $12$ 边形。三只青蛙起初分别在 $A_4$ 、 $A_8$ 和 $A_{12}$ 上。每分钟结束时，三只青蛙同时各自跳到当前顶点相邻的两个顶点之一，两个选择等可能且彼此独立。只要有两只青蛙同时到达同一个顶点，三只青蛙就都停止跳跃。青蛙停止跳跃前的期望分钟数为 $\frac{m}{n}$ ，其中 $m$ 与 $n$ 是互质正整数。求 $m + n$ 。

Let $A_1A_2A_3 \ldots A_{12}$ be a dodecagon ( $12$ -gon). Three frogs initially sit at $A_4,$ $A_8,$ and $A_{12}.$ At the end of each minute, simultaneously, each of the three frogs jumps to one of the two vertices adjacent to its current position, chosen randomly and independently with both choices being equally likely. All three frogs stop jumping as soon as two frogs arrive at the same vertex at the same time. The expected number of minutes until the frogs stop jumping is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

答案：19

知识点：期望值随机游走递推概率

难度评级：3160

解答：

追踪圆周上相邻青蛙之间的三个间隔；它们从 $(4, 4, 4)$ 开始，且总和始终为 $12$ 。若三只青蛙的跳跃方向为 $X_1, X_2, X_3 \in \{\pm 1\}$ ，则三个间隔分别改变 $X_2 - X_1$ 、 $X_3 - X_2$ 、 $X_1 - X_3$ ，所以每个间隔保持偶数，并且过程恰在某个间隔变为 $0$ 时停止。枚举 $8$ 种等可能的符号选择：从 $\{4,4,4\}$ 出发，以概率 $\frac{2}{8}$ 留在原状态，以概率 $\frac{6}{8}$ 转到 $\{2,4,6\}$ 。从 $\{2,4,6\}$ 出发，以概率 $\frac{4}{8}$ 留在原状态，以概率 $\frac{1}{8}$ 分别转到 $\{4,4,4\}$ 或 $\{2,2,8\}$ ，并以概率 $\frac{2}{8}$ 停止。从 $\{2,2,8\}$ 出发，以概率 $\frac{2}{8}$ 留在原状态，以概率 $\frac{2}{8}$ 转到 $\{2,4,6\}$ ，并以概率 $\frac{4}{8}$ 停止。

设 $E_1, E_2, E_3$ 分别为从 $\{4,4,4\}$ 、 $\{2,4,6\}$ 、 $\{2,2,8\}$ 。出发的剩余期望时间。则第三式给出 $E_3 = \frac{4}{3} + \frac{E_2}{3}$ ；代入第二式得 $E_2 = 4$ ，于是 $E_3 = \frac{8}{3}$ ，且 $E_1 = \frac{4}{3} + E_2 = \frac{16}{3}$ 。 $\begin{aligned} E_1 &= 1 + \tfrac{1}{4}E_1 + \tfrac{3}{4}E_2, \\ E_2 &= 1 + \tfrac{1}{2}E_2 + \tfrac{1}{8}E_1 \\ &\quad {}+ \tfrac{1}{8}E_3, \\ E_3 &= 1 + \tfrac{1}{4}E_3 + \tfrac{1}{4}E_2. \end{aligned}$

期望分钟数为 $\frac{16}{3}$ ，所以 $m + n = 16 + 3 = 19$ 。

Track the three gaps between consecutive frogs around the circle; they start at $(4, 4, 4)$ and always sum to $12.$ If the frogs jump by $X_1, X_2, X_3 \in \{\pm 1\},$ the gaps change by $X_2 - X_1,$ $X_3 - X_2,$ $X_1 - X_3,$ so each gap stays even and the process stops exactly when some gap becomes $0.$ Enumerating the $8$ equally likely sign choices: from $\{4,4,4\},$ the state stays with probability $\frac{2}{8}$ and moves to $\{2,4,6\}$ with probability $\frac{6}{8}.$ From $\{2,4,6\}:$ stay with probability $\frac{4}{8},$ move to $\{4,4,4\}$ or $\{2,2,8\}$ with probability $\frac{1}{8}$ each, and stop with probability $\frac{2}{8}.$ From $\{2,2,8\}:$ stay with probability $\frac{2}{8},$ move to $\{2,4,6\}$ with probability $\frac{2}{8},$ and stop with probability $\frac{4}{8}.$

Let $E_1, E_2, E_3$ be the expected remaining times from $\{4,4,4\},$ $\{2,4,6\},$ $\{2,2,8\}.$ Then $\begin{aligned} E_1 &= 1 + \tfrac{1}{4}E_1 + \tfrac{3}{4}E_2, \\ E_2 &= 1 + \tfrac{1}{2}E_2 + \tfrac{1}{8}E_1 \\ &\quad {}+ \tfrac{1}{8}E_3, \\ E_3 &= 1 + \tfrac{1}{4}E_3 + \tfrac{1}{4}E_2. \end{aligned}$ The third gives $E_3 = \frac{4}{3} + \frac{E_2}{3};$ substituting into the second yields $E_2 = 4,$ then $E_3 = \frac{8}{3}$ and $E_1 = \frac{4}{3} + E_2 = \frac{16}{3}.$

The expected number of minutes is $\frac{16}{3},$ so $m + n = 16 + 3 = 19.$

2021 AIME I 第 12 题

答案：19

难度评级：3160

解答：

其他年份的第 12 题