Skip to main content

2014 AMC 12B Problem 22

Problem 22 of 25HarderProbability & StatisticsProblem-Solving Techniques

In a small pond there are eleven lily pads in a row labeled 00 through 10.10. A frog is sitting on pad 1.1. When the frog is on pad N,N, 0<N<10,0 \lt N \lt 10, it will jump to pad N−1N - 1 with probability N10\dfrac{N}{10} and to pad N+1N + 1 with probability 1−N10.1 - \dfrac{N}{10}. Each jump is independent of the previous jumps. If the frog reaches pad 00 it will be eaten by a patiently waiting snake. If the frog reaches pad 1010 it will exit the pond, never to return. What is the probability that the frog will escape being eaten by the snake?

Answer choices

Show solution

Solution

Let pjp_j be the probability of eventually reaching pad 1010 starting from pad j.j. By the symmetry of the jump rule at the center, p5=12.p_5 = \tfrac12. Each interior pad satisfies pj=10−j10 pj+1+j10 pj−1,p_j = \tfrac{10-j}{10}\,p_{j+1} + \tfrac{j}{10}\,p_{j-1}, which gives p4=25p3+35p5,p3=310p2+710p4, \begin{gathered} p_4 = \tfrac25 p_3 + \tfrac35 p_5, \\ \quad p_3 = \tfrac{3}{10} p_2 + \tfrac{7}{10} p_4, \end{gathered} p2=15p1+45p3,p1=910p2. p_2 = \tfrac15 p_1 + \tfrac45 p_3,\quad p_1 = \tfrac{9}{10} p_2. Put dj=pj−pj−1.d_j=p_j-p_{j-1}. The recurrence is equivalent to (10−j)dj+1=jdj,(10-j)d_{j+1}=jd_j, so d2=d19,d3=d136,d4=d184,d5=d1126. \begin{gathered} d_2=\dfrac{d_1}{9},\quad d_3=\dfrac{d_1}{36}, \\ d_4=\dfrac{d_1}{84},\quad d_5=\dfrac{d_1}{126}. \end{gathered} Since p0=0p_0=0 and p5=12,p_5=\frac{1}{2}, 12=d1(1+19+136+184+1126)=d1⋅7363. \begin{aligned} \dfrac12&=d_1\biggl(1+\dfrac19+\dfrac1{36} \\ &\qquad+\dfrac1{84}+\dfrac1{126}\biggr) \\ &=d_1\cdot\dfrac{73}{63}. \end{aligned} Therefore p1=d1=63146.p_1=d_1=\frac{63}{146}. Thus, the correct answer is C.
AoPS wiki

Tagged: random walk · recursive probability · symmetry

More practice