Question

一只虫子从等边三角形的一个顶点出发。每一步，它随机选择当前不在的另外两个顶点之一，并沿着三角形的一条边爬到该顶点。已知这只虫子在第十步移动到其起始顶点的概率为 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质的正整数，求 $m + n$ 。

A bug starts at a vertex of an equilateral triangle. On each move, it randomly selects one of the two vertices where it is not currently located, and crawls along a side of the triangle to that vertex. Given that the probability that the bug moves to its starting vertex on its tenth move is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers, find $m + n.$

答案

答案：683

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

难度评级：2650

解答：

设 $p_n$ 为虫子在走完 $n$ 步后位于起始顶点的概率，因此 $p_0 = 1$ 。虫子在第 $n + 1$ 步后回到起点，当且仅当它在第 $n$ 步后位于别处（概率为 $1 - p_n$ ），然后选择起始顶点（概率为 $\frac{1}{2}$ ）： $p_{n+1} = \frac{1}{2}(1 - p_n).$

这个递推的不动点为 $\frac{1}{3}$ ，且 $p_{n+1} - \frac{1}{3} = -\frac{1}{2}\left(p_n - \frac{1}{3}\right)$ ，所以 $p_n = \frac{1}{3} + \frac{2}{3}\left(-\frac{1}{2}\right)^n$ 。

当 $n = 10$ ：时： $\begin{aligned} p_{10} &= \frac{1}{3}\left(1 + \frac{2}{1024}\right) \\ &= \frac{1}{3} \cdot \frac{1026}{1024} = \frac{171}{512}. \end{aligned}$ 因为 $171 = 9 \cdot 19$ 与 $512 = 2^9$ 没有公因数， $m + n = 171 + 512 = 683$ 。

Let $p_n$ be the probability that the bug is at its starting vertex after $n$ moves, so $p_0 = 1.$ The bug is home after move $n + 1$ exactly when it was elsewhere after move $n$ (probability $1 - p_n$ ) and then chose the starting vertex (probability $\frac{1}{2}$ ): $p_{n+1} = \frac{1}{2}(1 - p_n).$

The fixed point of this recurrence is $\frac{1}{3},$ and $p_{n+1} - \frac{1}{3} = -\frac{1}{2}\left(p_n - \frac{1}{3}\right),$ so $p_n = \frac{1}{3} + \frac{2}{3}\left(-\frac{1}{2}\right)^n.$

For $n = 10:$ $\begin{aligned} p_{10} &= \frac{1}{3}\left(1 + \frac{2}{1024}\right) \\ &= \frac{1}{3} \cdot \frac{1026}{1024} = \frac{171}{512}. \end{aligned}$ Since $171 = 9 \cdot 19$ and $512 = 2^9$ share no factor, $m + n = 171 + 512 = 683.$

2003 AIME II 第 13 题

答案：683

难度评级：2650

解答：

其他年份的第 13 题