## 2014 AMC 10B Problem 25 / 2014 AMC 12B Problem 22

2014 AMC 10B 25 / AMC 12B 22. In a small pond there are eleven lily pads in a row labeled 0 through 10. A frog is sitting on pad 1. When the frog is on pad N, 0 < N < 10, it will jump to pad – 1 with probability $\frac{N}{10}$ and to pad N + 1 with probability $1 - \frac{N}{10}$. Each jump is independent of the previous jumps. If the frog reaches pad 0 it will be eaten by a patiently waiting snake. If the frog reaches pad 10 it will exit the pond, never to return. What is the probability that the frog will escape being eaten by the snake?

(A) $\frac{32}{79}$   (B) $\frac{161}{384}$   (C) $\frac{63}{146}$   (D) $\frac{7}{16}$   (E) $\frac{1}{2}$

Let’s make sure we understand the set-up of the problem by drawing a state diagram:

The diagram above shows the probabilities which dictate the frog’s movement. The probability which we are supposed to find is $\mathbb{P} \{ \text{reach pad 10 when starting from pad 1}\}$.

A first line of attack could be to enumerate all possible paths from pad 1 to pad 10, then add up the probabilities of those paths. That doesn’t seem to work though: there are an infinite number of paths from pad 1 to pad 10 (imagine the frog “oscillating” between pads 1 and 2 before moving to pad 10), and there is no obvious way to sum up those probabilities.

The next thing that we could try is to move the frog one step and see if that simplifies the problem. From pad 1, the frog can only move to 2 places: pad 0 with probability 1/10 and pad 2 with probability 9/10. Hence,

\begin{aligned} \mathbb{P} \{ \text{reach pad 10 when starting from pad 1} \} &= \frac{1}{10} \mathbb{P} \{ \text{reach pad 10 when starting from pad 0}\} \\ &\hspace{1em} + \frac{9}{10} \mathbb{P} \{ \text{reach pad 10 when starting from pad 2}\}.\end{aligned}

Letting $p_i = \mathbb{P} \{ \text{reach pad 10 when starting from pad } i \}$, the equation above becomes

$p_1 = \frac{1}{10} p_0 + \frac{9}{10}p_2.$

Since the snake is on pad 0 and will eat the frog once the frog is on pad 0, $p_0 = 0$. Thus, if we can get $p_2$, we can solve for $p_1$. How can we derive an expression for $p_2$? Well, we could let the frog take another step forward! Since the frog can only move to pad 1 with probability 2/10 and pad 3 with probability 8/10, we must have

$p_2 = \frac{2}{10} p_1 + \frac{8}{10} p_3.$

Now we have 2 equations in 3 variables (i.e. $p_1$, $p_2$, and $p_3$), which is not enough to solve for the variables. But we can keep generating similar equations by considering where the frog can move from pad $i$! Hence, $p_0, \dots, p_{10}$ must satisfy the following system of equations:

$\begin{cases} p_0 &= 0, \\ p_1 &= \frac{1}{10} p_0 + \frac{9}{10} p_2, \\ p_2 &= \frac{2}{10} p_1 + \frac{8}{10} p_3, \\ &\vdots \\ p_9 &= \frac{9}{10} p_8 + \frac{1}{10} p_{10}, \\ p_{10} &= 1. \end{cases}$

There are a total of 11 equations in 11 variables, hence we should be able to solve for them.

In a competition, if you are unable to think of anything ingenious, you can solve for $p_1$ by using Gaussian elimination to solve the simultaneous equations. This link shows one ingenious method of simplifying the “brute force” solving of simultaneous equations: by noticing that $p_5 = 1/2$ due to the symmetry of the problem.

Let me show you of another method I thought of when trying to solve this problem. After looking at the equation $p_1 = \frac{1}{10} p_0 + \frac{9}{10} p_2$ for some time, I realised that I could think of $p_1$ as a weighted average of $p_0$ and $p_2$. That is to say, $p_1$ is 1 part $p_0$ and 9 parts $p_2$. If I were to draw these 3 numbers on a number line, then the ratio of the distance from $p_0$ to $p_1$ to the distance from $p_1$ to $p_2$ must be 9:1, as in the diagram below:

We can use the same logic for $p_2, p_3, \dots$ to get the ratios of the spaces from $p_0$ to $p_{10}$:

Simplifying the ratios:

Unifying them into one big ratio:

Thus,

\begin{aligned} p_1 &= \frac{252}{252 + 28 + 7 + 3 + 2 + 2 + 3 + 7 + 28 + 252} \\ &= \frac{252}{584} \\ &= \boldsymbol{\frac{63}{146}}.\end{aligned}