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

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)}}$ .

@@ Line 1: / Line 1: @@
 ==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==
-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==
-Consider – independently – every spot that the frog could attain.
+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>.
-Given that it can only jump at most <math>2</math> places per move, and still wishes to avoid pads <math>3</math> and <math>6</math>, it 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>.
-There are two ways to get to that point – one would be <math>(1,2)</math> on the first move, and the other is just <math>(2)</math>. The total sum is then <math>\frac{1}{2} \times \frac{1}{2} + \frac{1}{2} = \frac{3}{4}</math>, which put into our first column and move on. The frog must subsequently go to space <math>4</math>, again with probability <math>\frac{1}{2}</math>. Thus, be sure to multiply by <math>\frac{1}{2}</math> again, yielding the result of <math>\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>.
-Similarly, multiply your product by <math>\frac{1}{2}</math> once more, to arrive at spot <math>5</math>: <math>\frac{3}{8} \times {1}{2} = \frac{3}{16}</math>. For number <math>7</math>, take another <math>\frac{1}{2}, giving us </math>{3}{16} \times \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>.
-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 </math>(8,9,10)<math>, </math>(8,10)<math>, and </math>(9,10)<math>, as the path straight to point </math>10<math> is not available. That leaves us with a partial count of </math>\frac{1}{8} + \frac{1}{4} + \frac{1}{4} = frac{5}{8}<math>. Multiply, to find that </math>\frac{3}{32} \times {5}{8} = \boxed{\textbf{(A)} \frac{15}{256}}<math>. </math>\square$
+==Solution 3 (recursion)==
---anna0kear.
+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==
 {{AMC12 box|year=2019|ab=B|num-b=15|num-a=17}}
 {{MAA Notice}}
-−−−−−

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

Page

Toolbox

Search