Question

池塘中荷叶 $1, 2, 3, \ldots$ 排成一行。一只青蛙从荷叶 $1$ 。开始跳跃。从任意荷叶 $k$ 出发时，青蛙随机跳到 $k + 1$ 或 $k + 2$ ，两种选择的概率都是 $\frac{1}{2}$ ，且各次跳跃相互独立。青蛙经过荷叶 $7$ 的概率为 $\frac{p}{q}$ ，其中 $p$ 与 $q$ 是互质正整数。求 $p + q$ 。

Lily pads $1, 2, 3, \ldots$ lie in a row on a pond. A frog makes a sequence of jumps starting on pad $1.$ From any pad $k$ the frog jumps to either pad $k + 1$ or pad $k + 2$ chosen randomly with probability $\frac{1}{2}$ and independently of other jumps. The probability that the frog visits pad $7$ is $\frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. Find $p + q.$

答案

答案：107

知识点：递推概率递推

难度评级：2270

解答：

令 $p_k$ 为青蛙经过荷叶 $k$ 的概率。青蛙落在荷叶 $k$ 上恰有两种互斥方式：它经过荷叶 $k - 1$ 并从那里跳 $+1$ （若跳 $+2$ ，荷叶 $k$ 会永远被跳过），或者它完全跳过荷叶 $k - 1$ ，这要求它经过荷叶 $k - 2$ 并从那里跳 $+2$ ，落到荷叶 $k$ 。因此 $\begin{aligned} &p_k = \tfrac{1}{2}p_{k-1} + \tfrac{1}{2}p_{k-2}, \\ &\qquad p_1 = 1, \quad p_2 = \tfrac{1}{2}. \end{aligned}$

迭代得到 $p_3 = \frac{3}{4}$ 、 $p_4 = \frac{5}{8}$ 、 $p_5 = \frac{11}{16}$ 、 $p_6 = \frac{21}{32}$ 、 $p_7 = \frac{43}{64}$ 。因为 $\gcd(43, 64) = 1$ ，答案为 $43 + 64 = 107$ 。

Let $p_k$ be the probability that the frog visits pad $k.$ The frog lands on pad $k$ in exactly one of two disjoint ways: it visits pad $k - 1$ and jumps $+1$ from there (if it jumps $+2,$ pad $k$ is skipped forever), or it skips pad $k - 1$ entirely, which requires visiting pad $k - 2$ and jumping $+2$ from it, landing on pad $k.$ Hence $\begin{aligned} &p_k = \tfrac{1}{2}p_{k-1} + \tfrac{1}{2}p_{k-2}, \\ &\qquad p_1 = 1, \quad p_2 = \tfrac{1}{2}. \end{aligned}$

Iterating: $p_3 = \frac{3}{4},$ $p_4 = \frac{5}{8},$ $p_5 = \frac{11}{16},$ $p_6 = \frac{21}{32},$ and $p_7 = \frac{43}{64}.$ Since $\gcd(43, 64) = 1,$ the answer is $43 + 64 = 107.$

2019 AIME II 第 2 题

答案：107

难度评级：2270

解答：

其他年份的第 2 题