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 N – 1 with probability and to pad N + 1 with probability . 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) (B) (C) (D) (E)
Let’s make sure we understand the set-up of the problem by drawing a state diagram:
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,
Letting , the equation above becomes
Since the snake is on pad 0 and will eat the frog once the frog is on pad 0, . Thus, if we can get , we can solve for . How can we derive an expression for ? 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
Now we have 2 equations in 3 variables (i.e. , , and ), 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 ! Hence, must satisfy the following system of equations:
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 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 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 for some time, I realised that I could think of as a weighted average of and . That is to say, is 1 part and 9 parts . If I were to draw these 3 numbers on a number line, then the ratio of the distance from to to the distance from to must be 9:1, as in the diagram below:
Simplifying the ratios:
The answer is (C).