Recursive (Counting) AMC10/12 Difficult
2014


Problem - 473

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 $(N-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 without being eaten by the snake?


Let $P(N)$ be the frog's probability of survival when it is sitting on pad $N$. Then the desired answer is $P(1)$.

In the diagram below, numbered boxes denote the pads and the values above arrows show the probability when the frog jumps between corresponding pads.

Observing the above diagram reveals that the probability transitions when $N\le 5$ and those when $N\ge 5$ are symmetric. Hence, it must hold that $P(5)=\frac{1}{2}$.

When the frog sits on the $N^{th}$ pad, it can jump to either the $(N-1)^{th}$ or the $(N+1)^{th}$ pad. The corresponding survival probabilities are $P(N-1)$ and $P(N+1)$, respectively. This means that the frog's current survival rate will be a weighted average of these two , i.e.: $$P(N) = \frac{N}{10}\cdot P(N-1) + \left(1-\frac{N}{10}\right)\cdot P(N+1)$$

It follows that $$\left\{\begin{array}{rl}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)\\ \\P(3)=\ &\frac{3}{10}P(2) + \frac{7}{10}P(4)\\ \\P(4)=\ &\frac{4}{10}P(3)+\frac{6}{10}P(5)\\ \\P(5)=\ &\frac{1}{2}\end{array}\right.$$

Solving this system gives $$P(1)=\boxed{\frac{63}{146}}$$

report an error