Question

青蛙 Freddy 在坐标平面上跳来跳去寻找一条河，这条河位于水平直线 $y = 24$ 上。一道篱笆位于水平直线 $y = 0$ 上。每次跳跃时，Freddy 随机选择一个平行于某条坐标轴的方向，并朝该方向移动一个单位。当他位于 $y = 0$ 的点时，他以相等概率从三个方向中选择一个方向：要么平行于篱笆跳，要么远离篱笆跳，但他绝不会选择会越过篱笆进入 $y \lt 0$ 区域的方向。Freddy 从点 $(0, 21)$ 开始寻找，并会在到达河上的某点时停止。求 Freddy 到达河所需跳跃次数的期望值。

Freddy the frog is jumping around the coordinate plane searching for a river, which lies on the horizontal line $y = 24.$ A fence is located at the horizontal line $y = 0.$ On each jump Freddy randomly chooses a direction parallel to one of the coordinate axes and moves one unit in that direction. When he is at a point where $y = 0,$ with equal likelihoods he chooses one of three directions where he either jumps parallel to the fence or jumps away from the fence, but he never chooses the direction that would have him cross over the fence to where $y \lt 0.$ Freddy starts his search at the point $(0, 21)$ and will stop once he reaches a point on the river. Find the expected number of jumps it will take Freddy to reach the river.

答案

答案：273

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

难度评级：3270

解答：

水平跳跃不会改变任何重要信息，所以令 $T(y)$ 为从高度 $y$ 。到达河所需跳跃次数的期望。则 $T(24) = 0$ ；对于 $1 \le y \le 23$ ，每次跳跃以概率 $\frac{1}{4}, \frac{1}{4}, \frac{1}{2}$ ，分别向上、向下或水平移动，所以 $\begin{aligned} T(y) &= 1 + \tfrac{1}{4}T(y + 1) \\ &\quad {}+ \tfrac{1}{4}T(y - 1) \\ &\quad {}+ \tfrac{1}{2}T(y), \end{aligned}$ 化简得 $2T(y) = 4 + T(y - 1)$ $+ T(y + 1)$ 。在篱笆处，三个等可能移动给出 $T(0) = 1 + \frac{2}{3}T(0) + \frac{1}{3}T(1)$ ，即 $T(0) = 3 + T(1)$ 。

对 $y = 1, \ldots, 23$ 求和 $2T(y) = 4 + T(y - 1)$ $+ T(y + 1)$ ，望远镜相消得到 $T(1) + T(23) = 92 + T(0)$ $+ T(24)$ 。代入 $T(0) = 3 + T(1)$ 和 $T(24) = 0$ ，得到 $T(23) = 95$ 。

现在将递推式写成 $T(y - 1) = 2T(y) - T(y + 1)$ $- 4$ ：并向下推：由 $T(24) = 0$ 和 $T(23) = 95$ ，得到 $T(22) = 2 \cdot 95 - 0 - 4 = 186$ ，以及 $T(21) = 2 \cdot 186 - 95 - 4 = 273$ 。Freddy 从高度 $21$ ，开始，所以答案为 $273$ 。

Horizontal jumps change nothing that matters, so let $T(y)$ be the expected number of jumps to reach the river from height $y.$ Then $T(24) = 0;$ for $1 \le y \le 23$ each jump goes up, down, or sideways with probabilities $\frac{1}{4}, \frac{1}{4}, \frac{1}{2},$ so $\begin{aligned} T(y) &= 1 + \tfrac{1}{4}T(y + 1) \\ &\quad {}+ \tfrac{1}{4}T(y - 1) \\ &\quad {}+ \tfrac{1}{2}T(y), \end{aligned}$ which simplifies to $2T(y) = 4 + T(y - 1)$ $+ T(y + 1).$ At the fence the three equally likely moves give $T(0) = 1 + \frac{2}{3}T(0) + \frac{1}{3}T(1),$ that is $T(0) = 3 + T(1).$

Summing $2T(y) = 4 + T(y - 1)$ $+ T(y + 1)$ over $y = 1, \ldots, 23$ telescopes to $T(1) + T(23) = 92 + T(0)$ $+ T(24).$ Substituting $T(0) = 3 + T(1)$ and $T(24) = 0$ yields $T(23) = 95.$

Now run the recurrence downward as $T(y - 1) = 2T(y) - T(y + 1)$ $- 4:$ from $T(24) = 0$ and $T(23) = 95,$ we get $T(22) = 2 \cdot 95 - 0 - 4 = 186$ and $T(21) = 2 \cdot 186 - 95 - 4 = 273.$ Freddy starts at height $21,$ so the answer is $273.$

2016 AIME I 第 13 题

答案：273

难度评级：3270

解答：

其他年份的第 13 题