2014 AMC 10B Problem 25

Step 1: set up the unknowns. Let $p_N$ be the chance that the frog escapes if it is sitting on pad $N$. From pad $0$ it has been eaten, so $p_0 = 0$. From pad $10$ it has escaped, so $p_{10} = 1$. We want $p_1$.

Step 2: one jump. From pad $N$ the frog goes down with chance $\frac{N}{10}$ or up with chance $\frac{10 - N}{10}$, then carries on from the new pad. So
$$p_N = \frac{N}{10}\,p_{N-1} + \frac{10 - N}{10}\,p_{N+1}.$$

Step 3: look at the gaps. Ten equations like this are a lot of work, so look at the gaps between neighboring pads instead. Write $d_0 = p_1 - p_0$, $d_1 = p_2 - p_1$, and so on up to $d_9 = p_{10} - p_9$.

Multiply the equation in Step 2 by $10$, and write $10\,p_N$ as $N\,p_N + (10 - N)\,p_N$:
$$N\,p_N + (10 - N)\,p_N = N\,p_{N-1} + (10 - N)\,p_{N+1}.$$
Rearranging, $N\,(p_N - p_{N-1}) = (10 - N)\,(p_{N+1} - p_N)$. In gap language:
$$d_N = \frac{N}{10 - N}\, d_{N-1}.$$

Step 4: work out the gaps. Start from $d_0$ (which equals $p_1$, the answer we want):

The pads are balanced around pad $5$ (pad $N$ and pad $10 - N$ are mirror images, with snake and exit swapped), and the gaps come out the same way: $d_5 = d_4$, $d_6 = d_3$, $d_7 = d_2$, $d_8 = d_1$, $d_9 = d_0$. You can check this by carrying on with the factors $\frac64, \frac73, \frac82, \frac91$.

Step 5: the gaps add to 1. Adding all ten gaps climbs from $p_0 = 0$ to $p_{10} = 1$, so $d_0 + d_1 + \cdots + d_9 = 1$. Using the pairs from Step 4:
$$2 d_0 \left(1 + \frac19 + \frac{1}{36} + \frac{1}{84} + \frac{1}{126}\right) = 1.$$
With common denominator $252$, the bracket is $\frac{252 + 28 + 7 + 3 + 2}{252} = \frac{292}{252}$. So
$$2 d_0 \cdot \frac{292}{252} = 1, \qquad d_0 = \frac{252}{584} = \frac{63}{146}.$$

Step 6: answer. $p_1 = p_0 + d_0 = \frac{63}{146}$.

The answer is $\boxed{\textbf{(C)}\ \frac{63}{146}}$.

For a walk that ends when it hits one of two edges, writing "chance from here = average of chances after one step" gives an equation for every pad. Those equations are tangled, but the gaps between neighboring chances follow a simple multiply-by-a-factor rule. Since the gaps must add up to the total climb from $0$ to $1$, one sum finishes the problem. Watch for this "look at the differences" idea in any random-walk problem.

Use the mirror symmetry first: from pad $5$ the snake and the exit are equally far and the jump chances are balanced, so $p_5 = \frac12$. Now call $p_1 = a$ and march forward with the one-jump equation, solving each time for the next pad:
- from pad $1$: $a = \frac{9}{10}p_2$, so $p_2 = \frac{10a}{9}$;
- from pad $2$: $p_2 = \frac{2}{10}a + \frac{8}{10}p_3$, so $p_3 = \frac{41a}{36}$;
- from pad $3$: $p_3 = \frac{3}{10}p_2 + \frac{7}{10}p_4$, so $p_4 = \frac{145a}{126}$;
- from pad $4$: $p_4 = \frac{4}{10}p_3 + \frac{6}{10}p_5$, so $p_5 = \frac{73a}{63}$.

Setting $\frac{73a}{63} = \frac12$ gives $a = \frac{63}{146}$.

Let $p_N$ be the probability of escaping from pad $N$, so $p_0 = 0$ and $p_{10} = 1$. One jump from pad $N$ gives
$$p_N = \frac{N}{10}\,p_{N-1} + \frac{10 - N}{10}\,p_{N+1}.$$
Move $p_N$ across: $N(p_N - p_{N-1}) = (10 - N)(p_{N+1} - p_N)$. Writing $d_N = p_{N+1} - p_N$, this is
$$d_N = \frac{N}{10 - N}\, d_{N-1}.$$
So $d_1 = \frac{1}{9} d_0$, $d_2 = \frac{2}{8} \cdot \frac{1}{9} d_0 = \frac{d_0}{36}$, $d_3 = \frac{3}{7} \cdot \frac{d_0}{36} = \frac{d_0}{84}$, $d_4 = \frac{4}{6} \cdot \frac{d_0}{84} = \frac{d_0}{126}$; in general $d_N = \frac{d_0}{\binom{9}{N}}$, which is symmetric ($d_{9-N} = d_N$).

The differences telescope: $d_0 + d_1 + \cdots + d_9 = p_{10} - p_0 = 1$. Hence
$$1 = 2 d_0\left(1 + \frac19 + \frac{1}{36} + \frac{1}{84} + \frac{1}{126}\right) = 2 d_0 \cdot \frac{252 + 28 + 7 + 3 + 2}{252} = d_0 \cdot \frac{292}{126} = d_0 \cdot \frac{146}{63}.$$
So $d_0 = \frac{63}{146}$, and since $p_1 = p_0 + d_0$, the frog escapes with probability $\frac{63}{146}$.

The answer is $\boxed{\textbf{(C)}\ \frac{63}{146}}$.