Question

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.$

Answer

Answer: 107

Concepts:recursive probability recursion

Difficulty rating: 2270

Solution:

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 Problem 2

Answer: 107

Difficulty rating: 2270

Solution:

Problem 2 in Other Years