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"

(→‎Solution)
 
(47 intermediate revisions by 14 users not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
 +
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>?
  
−
==Solution==
+
<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>
−
We solve for the probability by doing <math>\frac{1-(Probability of Equality)}{2}</math>.
 
  
−
We see that the probability of equality is the summation of all the probabilities that the balls land in the same container. Thus we have the probability of equality being equal to <math>(\frac{1}{2})(\frac{1}{2})+(\frac{1}{4})(\frac{1}{4})+(\frac{1}{16})(\frac{1}{16})...</math>  
+
==Solution 1==
 +
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>.
  
−
The summation of this expression is equal to <cmath>\sum_{n=0}^{\infty} (1)(\frac{1}{4})^{n}-1</cmath>. Using the geometric sum formula, we obtain the summation of this expression to be <math>\frac{1}{\frac{3}{4}}-1</math> or <math>\frac{1}{3}</math>.
+
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 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 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, 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==
 +
 
 +
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>.
 +
 
 +
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>.
 +
 
 +
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>.
 +
 
 +
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)==
 +
 
 +
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>
 +
 
 +
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:
 +
 
 +
<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}}

Latest revision as of 23:33, 13 November 2022

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=181388"