2025 AMC 10B Problem 24

P21-25~6 minPrint

Basic Probability Systems of Equations Define states/recurrence and iterate Collapse a sum or product by cancellation

A frog hops along the number line according to the following rules.

$\qquad\bullet$ It starts at $0$ .

$\qquad\bullet$ If it is at $0$ , then it moves to $1$ with probability $\tfrac{1}{2}$ and it disappears with probability $\tfrac{1}{2}$ .

$\qquad\bullet$ For $n = 1, 2,$ or $3,$ if it is at $n,$ then it moves to $n+1$ with probability $\tfrac{1}{4},$ it moves to $n-1$ with probability $\tfrac{1}{4},$ and it disappears with $\qquad\phantom{\bullet}$ probability $\tfrac{1}{2}$ .

What is the probability that the frog reaches ${4\,?}$

Show solution without answering

Key insight

Let p1, p2, p3 be the chances of reaching 4 from 1, 2, 3. Each is a quarter of the chances one step down and one step up.

Solution

The frog can wander back and forth many times before reaching $4$ , so listing paths would never end. Instead, give each starting spot its own unknown.

Name the unknowns. Let $p_n$ be the chance of eventually reaching $4$ if the frog is now at $n$ . Then $p_4 = 1$ , and we want $p_0$ .

2. Look one hop ahead.
- From $0$ : half the time it moves to $1$ , otherwise it disappears. So $p_0 = \frac12 p_1$ .
- From $1$ : a quarter of the time it goes to $0$ , a quarter of the time to $2$ , and otherwise it disappears. So $p_1 = \frac14 p_0 + \frac14 p_2$ .
- In the same way, $p_2 = \frac14 p_1 + \frac14 p_3$ and $p_3 = \frac14 p_2 + \frac14 \cdot 1$ .

3. Write everything using $p_1$ , working upward.
- Multiply the second equation by $4$ : $4p_1 = p_0 + p_2 = \frac12 p_1 + p_2$ . So $p_2 = \frac72 p_1$ .
- Multiply the third by $4$ : $4p_2 = p_1 + p_3$ . So $p_3 = 4 \cdot \frac72 p_1 - p_1 = 14p_1 - p_1 = 13p_1$ .

4. Use the last equation to find $p_1$ . Multiply it by $4$ : $4p_3 = p_2 + 1$ . Substitute:
$52p_1 = \tfrac72 p_1 + 1 \quad\Longrightarrow\quad \left(52 - \tfrac72\right)p_1 = 1 \quad\Longrightarrow\quad \tfrac{97}{2}\,p_1 = 1 \quad\Longrightarrow\quad p_1 = \frac{2}{97}.$

Finish. $p_0 = \frac12 p_1 = \frac{1}{97}$ .

The answer is $\boxed{\textbf{(E)}\ \frac{1}{97}}$ .

Why this works

What happens next depends only on where the frog is now, not on how it got there. So one unknown for each spot, plus "what can the next hop do?", replaces an endless list of back-and-forth paths with four short equations. Writing each unknown as a multiple of $p_1$ from the bottom up leaves one equation with one unknown at the end.

Alternative approach

Climb one step at a time. Let $u_n$ be the chance that a frog at $n$ ever reaches $n + 1$ .
- From $0$ there is no way back, so $u_0 = \frac12$ .
- From $n \ge 1$ : it steps up right away with chance $\frac14$ ; or it steps down (chance $\frac14$ ), must climb back to $n$ (chance $u_{n-1}$ ), and then is in the same spot as before (chance $u_n$ ). So $u_n = \frac14 + \frac14 u_{n-1} u_n$ , which rearranges to $u_n = \dfrac{1}{4 - u_{n-1}}$ .

This gives $u_1 = \frac{1}{4 - 1/2} = \frac27$ , $u_2 = \frac{1}{4 - 2/7} = \frac{7}{26}$ , $u_3 = \frac{1}{4 - 7/26} = \frac{26}{97}$ . To reach $4$ the frog must climb every step, so
$\frac12 \cdot \frac27 \cdot \frac{7}{26} \cdot \frac{26}{97} = \frac{1}{97}.$

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

For $n = 0,1,2,3,4$ let $p_n$ be the probability that the frog ever reaches $4$ , given that it is sitting at $n$ . Then $p_4 = 1$ , and disappearing contributes $0$ . Each hop has probability at least $\tfrac12$ of ending the walk, so the frog is certain to disappear or reach $4$ eventually and these probabilities are well defined.

Condition on the next hop:
$p_0 = \tfrac12 p_1, \qquad p_1 = \tfrac14\left(p_0 + p_2\right), \qquad p_2 = \tfrac14\left(p_1 + p_3\right), \qquad p_3 = \tfrac14\left(p_2 + 1\right).$

Rather than eliminate blindly, express everything in terms of $p_1$ , working up the line.

From the second equation, $4p_1 = p_0 + p_2 = \tfrac12 p_1 + p_2$ , so
$p_2 = \tfrac72 p_1 .$
From the third, $4p_2 = p_1 + p_3$ , so
$p_3 = 4 \cdot \tfrac72 p_1 - p_1 = 13 p_1 .$
From the fourth, $4p_3 = p_2 + 1$ , so
$52 p_1 = \tfrac72 p_1 + 1 \implies \tfrac{97}{2} p_1 = 1 \implies p_1 = \frac{2}{97}.$

Finally $p_0 = \tfrac12 p_1 = \dfrac{1}{97}$ .

The answer is $\boxed{\textbf{(E)}\ \frac{1}{97}}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 7: Introduction to Probability
Introduction to Algebra, Chapter 5: Multi-Variable Linear Equations (§5.2, §5.3, §5.6)
Intermediate Counting & Probability, Chapter 10: Recursion
Introduction to Algebra, Chapter 21: Sequences & Series (§21.5)