Difference between revisions of "2019 AMC 12B Problems/Problem 16"

(Solution 3 (Recursion))
(Solution 3 (Recursion))
Line 34: Line 34:
 
<cmath>p_n = \frac{1}{2} \cdot p_{n-1} + \frac{1}{2} \cdot p_{n-2}</cmath>
 
<cmath>p_n = \frac{1}{2} \cdot p_{n-1} + \frac{1}{2} \cdot p_{n-2}</cmath>
  
This is because, given that we are at lily pad <math>n-2</math>, there is a 50% chance that we will go to lilypad <math>n</math>, and the same applies for lily pad <math>n-1</math>. We will now compute the values of <math>p_n</math> recursively, but we will skip over <math>3</math> and <math>6</math>. That is, we will not consider any jumps from lily pads 3 or 6 when considering the probabilities. We obtain the following chart:
+
This is because, given that we are at lily pad <math>n-2</math>, there is a 50% chance that we will go to lily pad <math>n</math>, and the same applies for lily pad <math>n-1</math>. We will now compute the values of <math>p_n</math> recursively, but we will skip over <math>3</math> and <math>6</math>. That is, we will not consider any jumps from lily pads 3 or 6 when considering the probabilities. We obtain the following chart:
  
 
<asy>
 
<asy>
 +
 +
unitsize(40);
 +
string[] vals = {"1", "$1/2$", "$3/4$", "$X$", "$3/8$", "$3/26$", "$X$", "$3/32$", "$3/64$", "$9/128$", "$15/256$", "$X$"};
 
for(int i =0; i<= 11; ++i) {
 
for(int i =0; i<= 11; ++i) {
 
draw((i,0)--(i+1,0)--(i+1,1)--(i,1)--cycle);
 
draw((i,0)--(i+1,0)--(i+1,1)--(i,1)--cycle);
 +
label((string) i, (i+0.5,0), S);
 +
label(vals[i], (i+0.5, 0.5));
 
}
 
}
 
</asy>
 
</asy>
 +
 +
As we can see, the answer is <math>\boxed{\textbf{(C) } \frac{15}{256}}</math>
  
 
==See Also==
 
==See Also==
 
{{AMC12 box|year=2019|ab=B|num-b=15|num-a=17}}
 
{{AMC12 box|year=2019|ab=B|num-b=15|num-a=17}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 00:33, 15 February 2019

Problem

Lily pads numbered from $0$ to $11$ lie in a row on a pond. Fiona the frog sits on pad $0$, a morsel of food sits on pad $10$, and predators sit on pads $3$ and $6$. At each unit of time the frog jumps either to the next higher numbered pad or to the pad after that, each with probability $\frac{1}{2}$, independently from previous jumps. What is the probability that Fiona skips over pads $3$ and $6$ and lands on pad $10$?

$\textbf{(A) }\frac{15}{256}\qquad\textbf{(B) }\frac{1}{16}\qquad\textbf{(C) }\frac{15}{128}\qquad\textbf{(D) }\frac{1}{8}\qquad\textbf{(E) }\frac{1}{4}$

Solution 1

First, notice that Fiona, if she jumps over the predator on pad $3$, must land on pad $4$. Similarly, she must land on $7$ if she makes it past $6$. Thus, we can split it into $3$ smaller problems counting the probability Fiona skips $3$, Fiona skips $6$ (starting at $4$) and $\textit{doesn't}$ skip $10$ (starting at $7$). Incidentally, the last one is equivalent to the first one minus $1$.

Let's call the larger jump a $2$-jump, and the smaller a $1$-jump.

For the first mini-problem, let's see our options. Fiona can either go $1, 1, 2$ (probability of $\frac{1}{8}$), or she can go $2, 2$ (probability of $\frac{1}{4}$). These are the only two options, so they together make the answer $\frac{3}{8}$. We now also know the answer to the last mini-problem ($\frac{5}{8}$).

For the second mini-problem, Fiona $\textit{must}$ go $1, 2$ (probability of $\frac{1}{4}$). Any other option results in her death to a predator.

Thus, the final answer is $\frac{3}{8} \cdot \frac{1}{4} \cdot \frac{5}{8} = \frac{15}{256} = \boxed{\textbf{(A) }\frac{15}{256}}$.

Solution 2

Consider – independently – every spot that the frog could attain.

Given that it can only jump at most $2$ places per move, and still wishes to avoid pads $3$ and $6$, it must also land on numbers $2$, $4$, $5$, and $7$.

There are two ways to get to that point – one would be $(1,2)$ on the first move, and the other is just $(2)$. The total sum is then $\frac{1}{2} \times \frac{1}{2} + \frac{1}{2} = \frac{3}{4}$, which put into our first column and move on. The frog must subsequently go to space $4$, again with probability $\frac{1}{2}$. Thus, be sure to multiply by $\frac{1}{2}$ again, yielding the result of $\frac{3}{8}$.

Similarly, multiply your product by $\frac{1}{2}$ once more, to arrive at spot $5$: $\frac{3}{8} \times {1}{2} = \frac{3}{16}$. For number $7$, take another $\frac{1}{2}$, giving us $\frac{3}{16} \times \frac{1}{2} = \frac{3}{32}$.

Next, we must look at a number of options. For a fuller picture, it would be best to break down the choices. The only possibilities here are $(8,9,10)$, $(8,10)$, and $(9,10)$, as the path straight to point $10$ is not available. That leaves us with a partial count of $\frac{1}{8} + \frac{1}{4} + \frac{1}{4} = frac{5}{8}$. Multiply, to find that $\frac{3}{32} \times \frac{5}{8} = \boxed{\textbf{(A)} \frac{15}{256}}$. $\square$

--anna0kear.

Solution 3 (Recursion)

Let $p_n$ be the probability of landing on lily pad $n$. We immediately notice that, if there are no restrictions: \[p_n = \frac{1}{2} \cdot p_{n-1} + \frac{1}{2} \cdot p_{n-2}\]

This is because, given that we are at lily pad $n-2$, there is a 50% chance that we will go to lily pad $n$, and the same applies for lily pad $n-1$. We will now compute the values of $p_n$ recursively, but we will skip over $3$ and $6$. That is, we will not consider any jumps from lily pads 3 or 6 when considering the probabilities. We obtain the following chart:

[asy]  unitsize(40); string[] vals = {"1", "$1/2$", "$3/4$", "$X$", "$3/8$", "$3/26$", "$X$", "$3/32$", "$3/64$", "$9/128$", "$15/256$", "$X$"}; for(int i =0; i<= 11; ++i) { draw((i,0)--(i+1,0)--(i+1,1)--(i,1)--cycle); label((string) i, (i+0.5,0), S); label(vals[i], (i+0.5, 0.5)); } [/asy]

As we can see, the answer is $\boxed{\textbf{(C) } \frac{15}{256}}$

See Also

2019 AMC 12B (ProblemsAnswer KeyResources)
Preceded by
Problem 15
Followed by
Problem 17
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png