Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(finishing sol'n. G)
m (→‎Solution 1)
 
(32 intermediate revisions by 13 users not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
−
Lily pads numbered from <math>0</math> to <math>11</math> lie in a row on a pond. Fiona the frog sits on pad <math>0</math>, a morsel of food sits on pad <math>10</math>, and predators sit on pads <math>3</math> and <math>6</math>. At each unit of time the frog jumps either to the next higher numbered pad or to the pad after that, each with probability <math>\frac{1}{2}</math>, independently from previous jumps. What is the probability that Fiona skips over pads <math>3</math> and <math>6</math> and lands on pad <math>10</math>?
+
There are lily pads in a row numbered <math>0</math> to <math>11</math>, in that order. There are predators on lily pads <math>3</math> and <math>6</math>, and a morsel of food on lily pad <math>10</math>. Fiona the frog starts on pad <math>0</math>, and from any given lily pad, has a <math>\frac{1}{2}</math> chance to hop to the next pad, and an equal chance to jump <math>2</math> pads. What is the probability that Fiona reaches pad <math>10</math> without landing on either pad <math>3</math> or pad <math>6</math>?
  
−
<math>\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}</math>
+
<math>\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) } \frac14</math>
  
 
==Solution 1==
 
==Solution 1==
−
First, notice that Fiona, if she jumps over the predator on pad <math>3</math>, must land on pad <math>4</math>. Similarly, she must land on <math>7</math> if she makes it past <math>6</math>. Thus, we can split it into <math>3</math> smaller problems counting the probability Fiona skips <math>3</math>, Fiona skips <math>6</math> (starting at <math>4</math>) and <math>\textit{doesn't}</math> skip <math>10</math> (starting at <math>7</math>). Incidentally, the last one is equivalent to the first one minus <math>1</math>.
+
Firstly, notice that if Fiona jumps over the predator on pad <math>3</math>, she must land on pad <math>4</math>. Similarly, she must land on <math>7</math> if she makes it past <math>6</math>. Thus, we can split the problem into <math>3</math> smaller sub-problems, separately finding the probability Fiona skips <math>3</math>, the probability she skips <math>6</math> (starting at <math>4</math>) and the probability she ''doesn't'' skip <math>10</math> (starting at <math>7</math>). Notice that by symmetry, the last of these three sub-problems is the complement of the first sub-problem, so the probability will be <math>1 - \text{the probability obtained in the first sub-problem}</math>.
  
−
Let's call the larger jump a <math>2</math>-jump, and the smaller a <math>1</math>-jump.  
+
In the analysis below, we call the larger jump a <math>2</math>-jump, and the smaller a <math>1</math>-jump.  
  
−
For the first mini-problem, let's see our options. Fiona can either go <math>1, 1, 2</math> (probability of <math>\frac{1}{8}</math>), or she can go <math>2, 2</math> (probability of <math>\frac{1}{4}</math>). These are the only two options, so they together make the answer <math>\frac{3}{8}</math>. We now also know the answer to the last mini-problem (<math>\frac{5}{8}</math>).
+
For the first sub-problem, consider Fiona's options. She can either go <math>1</math>-jump, <math>1</math>-jump, <math>2</math>-jump, with probability <math>\frac{1}{8}</math>, or she can go <math>2</math>-jump, <math>2</math>-jump, with probability <math>\frac{1}{4}</math>. These are the only two options, so they together make the answer <math>\frac{1}{8}+\frac{1}{4}=\frac{3}{8}</math>. We now also know the answer to the last sub-problem is <math>1-\frac{3}{8}=\frac{5}{8}</math>.
  
−
For the second mini-problem, Fiona <math>\textit{must}</math> go <math>1, 2</math> (probability of <math>\frac{1}{4}</math>). Any other option results in her death to a predator.
+
For the second sub-problem, Fiona ''must'' go <math>1</math>-jump, <math>2</math>-jump, with probability <math>\frac{1}{4}</math>, since any other option would result in her death to a predator.
  
−
Thus, the final answer is <math>\frac{3}{8} \cdot \frac{1}{4} \cdot \frac{5}{8} = \frac{15}{256} = \boxed{\textbf{(A) }\frac{15}{256}}</math>.
+
Thus, since the three sub-problems are independent, the final answer is <math>\frac{3}{8} \cdot \frac{1}{4} \cdot \frac{5}{8} = \boxed{\textbf{(A) }\frac{15}{256}}</math>.
  
 
==Solution 2==
 
==Solution 2==
  
−
A different, but longer (and more tedious) answer-checking approach would involve considering each spot that the frog could get to separately.
+
Observe that since Fiona can only jump at most <math>2</math> places per move, and still wishes to avoid pads <math>3</math> and <math>6</math>, she must also land on numbers <math>2</math>, <math>4</math>, <math>5</math>, and <math>7</math>.
  
−
Since we know it can only jump a maximum of 2 places at the time: as long as it wishes to avoid pads 3 and 6, it MUST land on numbers 2, 4, 5, and 7. Get it?
+
There are two ways to reach lily pad <math>2</math>, namely <math>1</math>-jump, <math>1</math>-jump, with probability <math>\frac{1}{4}</math>, or just a <math>2</math>-jump, with probability <math>\frac{1}{2}</math>. The total is thus <math>\frac{1}{4} + \frac{1}{2} = \frac{3}{4}</math>. Fiona must now make a <math>2</math>-jump to lily pad <math>4</math>, again with probability <math>\frac{1}{2}</math>, giving <math>\frac{3}{4} \cdot \frac{1}{2} = \frac{3}{8}</math>.
  
−
There's two ways to get there: either \tex(1,2) or just <math>2</math> for the first move. There's also a 1/4 chance that it skips. Thus, we put 3/4 into our column and then move on-fir now.
+
Similarly, Fiona must now make a <math>1</math>-jump to reach lily pad <math>5</math>, again with probability <math>\frac{1}{2}</math>, giving <math>\frac{3}{8} \cdot \frac{1}{2} = \frac{3}{16}</math>. Then she must make a <math>2</math>-jump to reach lily pad <math>7</math>, with probability <math>\frac{1}{2}</math>, yielding <math>\frac{3}{16} \cdot \frac{1}{2} = \frac{3}{32}</math>.
  
−
It must then make it to space #4, another 1/2 probability. So you can make sure to multiple by 1/2 again, giving 3/8.
+
Finally, to reach lily pad <math>10</math>, Fiona has a few options - she can make <math>3</math> consecutive <math>1</math>-jumps, with probability <math>\frac{1}{8}</math>, or <math>1</math>-jump, <math>2</math>-jump, with probability <math>\frac{1}{4}</math>, or <math>2</math>-jump, <math>1</math>-jump, again with probability <math>\frac{1}{4}</math>. The final answer is thus <math>\frac{3}{32} \cdot \left(\frac{1}{8} + \frac{1}{4} + \frac{1}{4}\right) = \frac{3}{32} \cdot \frac{5}{8} = \boxed{\textbf{(A) } \frac{15}{256}}</math>.
  
 +
==Solution 3 (recursion)==
  
−
It's going to be getting a bit different now: for the next few choices, it also has to get to 5. Since our probability has also given and taken into account the factor that it's already landed on 4, multiple by #5 again to get to the spot-ment: 3/8 * 1/2 = 3/16.
+
Let <math>p_n</math> be the probability of landing on lily pad <math>n</math>. Observe that if there are no restrictions, we would have
 +
<cmath>p_n = \frac{1}{2} \cdot p_{n-1} + \frac{1}{2} \cdot p_{n-2}</cmath>
  
−
Now there's another 1/2, giving us 3/16 * 1/2 = 3/32 for the erighther anosther. spot. lol then, we get to
+
This is because, given that Fiona is at lily pad <math>n-2</math>, there is a <math>\frac{1}{2}</math> probability that she will make a <math>2</math>-jump to reach lily pad <math>n</math>, and the same applies for a <math>1</math>-jump to reach 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 <math>3</math> or <math>6</math> when considering the probabilities. We obtain the following chart, where an X represents an unused/uncomputed value:
  
−
Here, we must look at possible options. There's only a 3/4 chance that it makes it directly. So, if we want a fuller picture then let's break it down. The possibilities are (8,9,10) (8,10) and (9,10) since going straight to #10 is not allowed. That leaves us with a partial count of 1/8 + 1/4 + 1/4 = 5/8 which we know works because the total sum can still add up to 1. Then, multiply, and that gives <math>3/32 * 5/8 = 15/256</math>.
+
<asy>
 +
 
 +
unitsize(40);
 +
string[] vals = {"1", "$1/2$", "$3/4$", "X", "$3/8$", "$3/16$", "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>
 +
 
 +
Hence the answer is <math>\boxed{\textbf{(A) } \frac{15}{256}}</math>.
 +
 
 +
Note: If we let <math>p_n</math> be the probability of surviving if the frog is on lily pad <math>n</math>, using <math>p_{10}</math> = 1, we can solve backwards and obtain the following chart:
 +
 
 +
<asy>
 +
 
 +
unitsize(40);
 +
string[] vals = {"$15/256$", "$5/128$", "$5/64$", "X", "$5/32$", "$5/16$", "X", "$5/8$", "$3/4$", "$1/2$", "1", "X"};
 +
for(int i =0; i<= 11; ++i) {
 +
draw((i,0)--(i+1,0)--(i+1,1)--(i,1)--cycle);
 +
label((string) (11-i), (i+0.5,0), S);
 +
label(vals[(11-i)], (i+0.5, 0.5));
 +
}
 +
</asy>
 +
 
 +
==Solution 4 (simple casework bash)==
 +
This is equivalent to finding the probability for each of the valid ways of tiling a <math>1</math>-by-<math>11</math> rectangular grid (with one end being lilypad <math>0</math> and the other being lilypad <math>11</math>) with tiles of size <math>1 \cdot 1</math> and <math>1 \cdot 2</math> that satisfies the conditions mentioned in the problem. Obviously, for Fiona to skip pads <math>3</math> and <math>6</math>, a <math>1 \cdot 2</math> tile must be placed with one end at lilypad <math>2</math> and the other at lilypad <math>4</math>, and another <math>1 \cdot 2</math> must be placed with one end at lilypad <math>5</math> and the other at lilypad <math>7</math>. Thus, since only a <math>1 \cdot 1</math> tile can fit between the two aforementioned <math>1 \cdot 2</math> tiles, we will place it there. Now, we can solve this problem with simple casework.
 +
 
 +
Case 1: Two <math>1 \cdot 1</math> tiles fill the space between lilypads <math>0</math> and <math>2</math>.
 +
 
 +
There are two ways to permute a placement of a <math>1 \cdot 1</math> tile and a <math>1 \cdot 2</math> tile between lilypads <math>7</math> and <math>10</math>, so our probability for this sub-case is <math>\frac{2}{2^7} = \frac{1}{64}</math>. In the other subcase where the space between lilypads <math>7</math> and <math>10</math> is completely filled with <math>1 \cdot 1</math> tiles, there is trivially only one tiling, thus the probability for this sub-case is <math>\frac{1}{2^8} = \frac{1}{256}.</math> The total probability for this case is <math>\frac{1}{64} + \frac{1}{256} = \frac{5}{256}.</math>
 +
 
 +
Case 2: A single <math>1 \cdot 2</math> tile fills the space between lilypads <math>0</math> and <math>2</math>.
 +
 
 +
Note that the combined probability for this case will be double that of Case <math>1</math>, since a single <math>1 \cdot 2</math> tile takes up one less tile than two <math>1 \cdot 1</math> tiles. Thus, the probability for this case is <math>2 \cdot \frac{5}{256} = \frac{10}{256}.</math>
 +
 
 +
Summing our cases up, we obtain <math>\boxed{\textbf{(A) } \frac{15}{256}}</math>.
 +
 
 +
-fidgetboss_4000
 +
 
 +
==Solution 5 (answer choices)==
 +
Note that there is exactly one way to reach lily pad <math>10</math> in <math>8</math> moves, and there is a probability of <math>\frac{1}{256}</math> that this occurs. All other paths take less than <math>8</math> moves, and thus the probability of them occurring is <math>\frac{n}{2^k}</math> for <math>k < 8</math>. Thus, the answer must have a denominator of <math>256</math>, or answer choice <math>\boxed{\textbf{(A)}}</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}}

Latest revision as of 08:32, 15 September 2024

Problem

There are lily pads in a row numbered $0$ to $11$, in that order. There are predators on lily pads $3$ and $6$, and a morsel of food on lily pad $10$. Fiona the frog starts on pad $0$, and from any given lily pad, has a $\frac{1}{2}$ chance to hop to the next pad, and an equal chance to jump $2$ pads. What is the probability that Fiona reaches pad $10$ without landing on either pad $3$ or pad $6$?

$\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) } \frac14$

Solution 1

Firstly, notice that if Fiona jumps over the predator on pad $3$, she must land on pad $4$. Similarly, she must land on $7$ if she makes it past $6$. Thus, we can split the problem into $3$ smaller sub-problems, separately finding the probability Fiona skips $3$, the probability she skips $6$ (starting at $4$) and the probability she doesn't skip $10$ (starting at $7$). Notice that by symmetry, the last of these three sub-problems is the complement of the first sub-problem, so the probability will be $1 - \text{the probability obtained in the first sub-problem}$.

In the analysis below, we call the larger jump a $2$-jump, and the smaller a $1$-jump.

For the first sub-problem, consider Fiona's options. She can either go $1$-jump, $1$-jump, $2$-jump, with probability $\frac{1}{8}$, or she can go $2$-jump, $2$-jump, with probability $\frac{1}{4}$. These are the only two options, so they together make the answer $\frac{1}{8}+\frac{1}{4}=\frac{3}{8}$. We now also know the answer to the last sub-problem is $1-\frac{3}{8}=\frac{5}{8}$.

For the second sub-problem, Fiona must go $1$-jump, $2$-jump, with probability $\frac{1}{4}$, since any other option would result in her death to a predator.

Thus, since the three sub-problems are independent, the final answer is $\frac{3}{8} \cdot \frac{1}{4} \cdot \frac{5}{8} = \boxed{\textbf{(A) }\frac{15}{256}}$.

Solution 2

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

There are two ways to reach lily pad $2$, namely $1$-jump, $1$-jump, with probability $\frac{1}{4}$, or just a $2$-jump, with probability $\frac{1}{2}$. The total is thus $\frac{1}{4} + \frac{1}{2} = \frac{3}{4}$. Fiona must now make a $2$-jump to lily pad $4$, again with probability $\frac{1}{2}$, giving $\frac{3}{4} \cdot \frac{1}{2} = \frac{3}{8}$.

Similarly, Fiona must now make a $1$-jump to reach lily pad $5$, again with probability $\frac{1}{2}$, giving $\frac{3}{8} \cdot \frac{1}{2} = \frac{3}{16}$. Then she must make a $2$-jump to reach lily pad $7$, with probability $\frac{1}{2}$, yielding $\frac{3}{16} \cdot \frac{1}{2} = \frac{3}{32}$.

Finally, to reach lily pad $10$, Fiona has a few options - she can make $3$ consecutive $1$-jumps, with probability $\frac{1}{8}$, or $1$-jump, $2$-jump, with probability $\frac{1}{4}$, or $2$-jump, $1$-jump, again with probability $\frac{1}{4}$. The final answer is thus $\frac{3}{32} \cdot \left(\frac{1}{8} + \frac{1}{4} + \frac{1}{4}\right) = \frac{3}{32} \cdot \frac{5}{8} = \boxed{\textbf{(A) } \frac{15}{256}}$.

Solution 3 (recursion)

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

This is because, given that Fiona is at lily pad $n-2$, there is a $\frac{1}{2}$ probability that she will make a $2$-jump to reach lily pad $n$, and the same applies for a $1$-jump to reach 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, where an X represents an unused/uncomputed value:

[asy] unitsize(40); string[] vals = {"1", "$1/2$", "$3/4$", "X", "$3/8$", "$3/16$", "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]

Hence the answer is $\boxed{\textbf{(A) } \frac{15}{256}}$.

Note: If we let $p_n$ be the probability of surviving if the frog is on lily pad $n$, using $p_{10}$ = 1, we can solve backwards and obtain the following chart:

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

Solution 4 (simple casework bash)

This is equivalent to finding the probability for each of the valid ways of tiling a $1$-by-$11$ rectangular grid (with one end being lilypad $0$ and the other being lilypad $11$) with tiles of size $1 \cdot 1$ and $1 \cdot 2$ that satisfies the conditions mentioned in the problem. Obviously, for Fiona to skip pads $3$ and $6$, a $1 \cdot 2$ tile must be placed with one end at lilypad $2$ and the other at lilypad $4$, and another $1 \cdot 2$ must be placed with one end at lilypad $5$ and the other at lilypad $7$. Thus, since only a $1 \cdot 1$ tile can fit between the two aforementioned $1 \cdot 2$ tiles, we will place it there. Now, we can solve this problem with simple casework.

Case 1: Two $1 \cdot 1$ tiles fill the space between lilypads $0$ and $2$.

There are two ways to permute a placement of a $1 \cdot 1$ tile and a $1 \cdot 2$ tile between lilypads $7$ and $10$, so our probability for this sub-case is $\frac{2}{2^7} = \frac{1}{64}$. In the other subcase where the space between lilypads $7$ and $10$ is completely filled with $1 \cdot 1$ tiles, there is trivially only one tiling, thus the probability for this sub-case is $\frac{1}{2^8} = \frac{1}{256}.$ The total probability for this case is $\frac{1}{64} + \frac{1}{256} = \frac{5}{256}.$

Case 2: A single $1 \cdot 2$ tile fills the space between lilypads $0$ and $2$.

Note that the combined probability for this case will be double that of Case $1$, since a single $1 \cdot 2$ tile takes up one less tile than two $1 \cdot 1$ tiles. Thus, the probability for this case is $2 \cdot \frac{5}{256} = \frac{10}{256}.$

Summing our cases up, we obtain $\boxed{\textbf{(A) } \frac{15}{256}}$.

-fidgetboss_4000

Solution 5 (answer choices)

Note that there is exactly one way to reach lily pad $10$ in $8$ moves, and there is a probability of $\frac{1}{256}$ that this occurs. All other paths take less than $8$ moves, and thus the probability of them occurring is $\frac{n}{2^k}$ for $k < 8$. Thus, the answer must have a denominator of $256$, or answer choice $\boxed{\textbf{(A)}}$.

See Also

2019 AMC 12B (Problems • Answer Key • Resources)
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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_AMC_12B_Problems/Problem_16&oldid=227243"