2014 AMC 10B Problem 25 / 2014 AMC 12B Problem 22

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 – 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 being eaten by the snake?

(A) \frac{32}{79}   (B) \frac{161}{384}   (C) \frac{63}{146}   (D) \frac{7}{16}   (E) \frac{1}{2}

Let’s make sure we understand the set-up of the problem by drawing a state diagram:

AMC_10B_25_01The diagram above shows the probabilities which dictate the frog’s movement. The probability which we are supposed to find is \mathbb{P} \{ \text{reach pad 10 when starting from pad 1}\}.

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,

\begin{aligned} \mathbb{P} \{ \text{reach pad 10 when starting from pad 1} \} &= \frac{1}{10} \mathbb{P} \{ \text{reach pad 10 when starting from pad 0}\} \\  &\hspace{1em} + \frac{9}{10} \mathbb{P} \{ \text{reach pad 10 when starting from pad 2}\}.\end{aligned}

Letting p_i = \mathbb{P} \{ \text{reach pad 10 when starting from pad } i \}, the equation above becomes

p_1 = \frac{1}{10} p_0 + \frac{9}{10}p_2.

Since the snake is on pad 0 and will eat the frog once the frog is on pad 0, p_0 = 0. Thus, if we can get p_2, we can solve for p_1. How can we derive an expression for p_2? 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

p_2 = \frac{2}{10} p_1 + \frac{8}{10} p_3.

Now we have 2 equations in 3 variables (i.e. p_1, p_2, and p_3), 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 i! Hence, p_0, \dots, p_{10} must satisfy the following system of equations:

\begin{cases} 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, \\  &\vdots \\  p_9 &= \frac{9}{10} p_8 + \frac{1}{10} p_{10}, \\  p_{10} &= 1. \end{cases}

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 p_1 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 p_5 = 1/2 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 p_1 = \frac{1}{10} p_0 + \frac{9}{10} p_2 for some time, I realised that I could think of p_1 as a weighted average of p_0 and p_2. That is to say, p_1 is 1 part p_0 and 9 parts p_2. If I were to draw these 3 numbers on a number line, then the ratio of the distance from p_0 to p_1 to the distance from p_1 to p_2 must be 9:1, as in the diagram below:

AMC_10B_25_02We can use the same logic for p_2, p_3, \dots to get the ratios of the spaces from p_0 to p_{10}:

AMC_10B_25_03

Simplifying the ratios:

AMC_10B_25_04Unifying them into one big ratio:

AMC_10B_25_05Thus,

\begin{aligned} p_1 &= \frac{252}{252 + 28 + 7 + 3 + 2 + 2 + 3 + 7 + 28 + 252} \\  &= \frac{252}{584} \\  &= \boldsymbol{\frac{63}{146}}.\end{aligned}

The answer is (C).

Advertisements
This entry was posted in Grade 10, Grade 12, USA and tagged , , . Bookmark the permalink.

2 Responses to 2014 AMC 10B Problem 25 / 2014 AMC 12B Problem 22

  1. Pingback: Penalty Shootout Wager | Beyond Solutions

  2. Pingback: Penalty Shootout Wager 2 | Beyond Solutions

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s