Problem:
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 10N and to pad N+1 with probability 1−10N. 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?
Answer Choices:
A. 7932
B. 384161
C. 14663
D. 167
E. 21
Solution:
First note that once the frog is on pad 5, it has probability 21 of eventually being eaten by the snake, and a probability 21 of eventually exiting the pond without being eaten. It is therefore necessary only to determine the probability that the frog on pad 1 will reach pad 5 before being eaten.
Consider the frog's jumps in pairs. The frog on pad 1 will advance to pad 3 with probability 109⋅108=10072, will be back at pad 1 with probability 109⋅102=10018, and will retreat to pad 0 and be eaten with probability 101. Because the frog will eventually make it to pad 3 or make it to pad 0 , the probability that it ultimately makes it to pad 3 is 10072÷(10072+10010)=4136, and the probability that it ultimately makes it to pad 0 is 10010÷(10072+10010)=415.
Similarly, in a pair of jumps the frog will advance from pad 3 to pad 5 with probability 107⋅106=10042, will be back at pad 3 with probability 107⋅104+103⋅108= 10052, and will retreat to pad 1 with probability 103⋅102=1006. Because the frog will ultimately make it to pad 5 or pad 1 from pad 3 , the probability that it ultimately makes it to pad 5 is 10042÷(10042+1006)=87, and the probability that it ultimately makes it to pad 1 is 1006÷(10042+1006)=81.
The sequences of pairs of moves by which the frog will advance to pad 5 without being eaten are
1→3→5,1→3→1→3→5,1→3→1→3→1→3→5
and so on. The sum of the respective probabilities of reaching pad 5 is then
4136⋅87+4136⋅81⋅4136⋅87+4136⋅81⋅4136⋅81⋅4136⋅87+⋯=8263(1+829+(829)2+⋯)=8263÷(1−829)
=7363.
Therefore the requested probability is 21⋅7363=14663.
OR
For 1≤j≤5, let pj be the probability that the frog eventually reaches pad 10 starting at pad j. By symmetry p5=21. For the frog to reach pad 10 starting from pad 4 , the frog goes either to pad 3 with probability 52 or to pad 5 with probability 53, and then continues on a successful sequence from either of these pads. Thus p4=52p3+53p5=52p3+103. Similarly, to reach pad 10 starting from pad 3 , the frog goes either to pad 2 with probability 103 or to pad 4 with probability 107. Thus p3=103p2+107p4, and substituting from the previous equation for p4 gives p3=125p2+247. In the same way, p2=51p1+54p3 and after substituting for p3 gives p2=103p1+207. Lastly, for the frog to escape starting from pad 1 , it is necessary for it to get to pad 2 with probability 109, and then escape starting from pad 2. Thus p1=109p2=109(103p1+207), and solving the equation gives p1=14663.
Note: This type of random process is called a Markov process.
The problems on this page are the property of the MAA's American Mathematics Competitions