Difference between revisions of "2019 AMC 12B Problems/Problem 16"
m (open-up. G'L) |
m (→Solution 1) |
||
(26 intermediate revisions by 12 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>? | |
− | <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) }\ | + | <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== | ||
− | + | 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>. | |
− | + | 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 | + | 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 | + | 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 | + | 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== | ||
− | + | 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}} | {{MAA Notice}} | ||
− |
Latest revision as of 09:32, 15 September 2024
Contents
Problem
There are lily pads in a row numbered to , in that order. There are predators on lily pads and , and a morsel of food on lily pad . Fiona the frog starts on pad , and from any given lily pad, has a chance to hop to the next pad, and an equal chance to jump pads. What is the probability that Fiona reaches pad without landing on either pad or pad ?
Solution 1
Firstly, notice that if Fiona jumps over the predator on pad , she must land on pad . Similarly, she must land on if she makes it past . Thus, we can split the problem into smaller sub-problems, separately finding the probability Fiona skips , the probability she skips (starting at ) and the probability she doesn't skip (starting at ). Notice that by symmetry, the last of these three sub-problems is the complement of the first sub-problem, so the probability will be .
In the analysis below, we call the larger jump a -jump, and the smaller a -jump.
For the first sub-problem, consider Fiona's options. She can either go -jump, -jump, -jump, with probability , or she can go -jump, -jump, with probability . These are the only two options, so they together make the answer . We now also know the answer to the last sub-problem is .
For the second sub-problem, Fiona must go -jump, -jump, with probability , since any other option would result in her death to a predator.
Thus, since the three sub-problems are independent, the final answer is .
Solution 2
Observe that since Fiona can only jump at most places per move, and still wishes to avoid pads and , she must also land on numbers , , , and .
There are two ways to reach lily pad , namely -jump, -jump, with probability , or just a -jump, with probability . The total is thus . Fiona must now make a -jump to lily pad , again with probability , giving .
Similarly, Fiona must now make a -jump to reach lily pad , again with probability , giving . Then she must make a -jump to reach lily pad , with probability , yielding .
Finally, to reach lily pad , Fiona has a few options - she can make consecutive -jumps, with probability , or -jump, -jump, with probability , or -jump, -jump, again with probability . The final answer is thus .
Solution 3 (recursion)
Let be the probability of landing on lily pad . Observe that if there are no restrictions, we would have
This is because, given that Fiona is at lily pad , there is a probability that she will make a -jump to reach lily pad , and the same applies for a -jump to reach lily pad . We will now compute the values of recursively, but we will skip over and . That is, we will not consider any jumps from lily pads or when considering the probabilities. We obtain the following chart, where an X represents an unused/uncomputed value:
Hence the answer is .
Note: If we let be the probability of surviving if the frog is on lily pad , using = 1, we can solve backwards and obtain the following chart:
Solution 4 (simple casework bash)
This is equivalent to finding the probability for each of the valid ways of tiling a -by- rectangular grid (with one end being lilypad and the other being lilypad ) with tiles of size and that satisfies the conditions mentioned in the problem. Obviously, for Fiona to skip pads and , a tile must be placed with one end at lilypad and the other at lilypad , and another must be placed with one end at lilypad and the other at lilypad . Thus, since only a tile can fit between the two aforementioned tiles, we will place it there. Now, we can solve this problem with simple casework.
Case 1: Two tiles fill the space between lilypads and .
There are two ways to permute a placement of a tile and a tile between lilypads and , so our probability for this sub-case is . In the other subcase where the space between lilypads and is completely filled with tiles, there is trivially only one tiling, thus the probability for this sub-case is The total probability for this case is
Case 2: A single tile fills the space between lilypads and .
Note that the combined probability for this case will be double that of Case , since a single tile takes up one less tile than two tiles. Thus, the probability for this case is
Summing our cases up, we obtain .
-fidgetboss_4000
Solution 5 (answer choices)
Note that there is exactly one way to reach lily pad in moves, and there is a probability of that this occurs. All other paths take less than moves, and thus the probability of them occurring is for . Thus, the answer must have a denominator of , or answer choice .
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.