Difference between revisions of "2021 AMC 12A Problems/Problem 23"
Isabelchen (talk | contribs) (→Solution 8 (Markov Chain)) |
Pi is 3.14 (talk | contribs) (→Video Solution by OmegaLearn (Using Probability States)) |
||
(34 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
− | {{duplicate|[[2021 AMC 10A Problems | + | {{duplicate|[[2021 AMC 10A Problems/Problem 23|2021 AMC 10A #23]] and [[2021 AMC 12A Problems/Problem 23|2021 AMC 12A #23]]}} |
==Problem== | ==Problem== | ||
Line 150: | Line 150: | ||
==Solution 8 (Markov Chain)== | ==Solution 8 (Markov Chain)== | ||
+ | The grid is symmetrical. Denote the center cell as state Center, the <math>4</math> middle side cells as state Side, the <math>4</math> corner cells as state Corner. We can draw the following State Transition Diagram with [https://en.wikipedia.org/wiki/Markov_chain Markov Chain]. The numbers on the transition arc are the transition probability. | ||
+ | [[File:Markov Chain(center side corner).png|900px|center]] | ||
− | + | We calculate the probability of different states in each round in the following table by iterating a few more times: | |
− | + | <!--[https://en.wikipedia.org/wiki/Dynamic_programming Dynamic Programming]:--> | |
− | |||
− | |||
<cmath>\begin{array}{|c|c|c|c|} | <cmath>\begin{array}{|c|c|c|c|} | ||
− | & \textbf{Center} & \textbf{Side} & \textbf{Corner}\\ | + | \hline |
+ | \textbf{Round} & \textbf{Center} & \textbf{Side} & \textbf{Corner}\\ | ||
\hline | \hline | ||
&&&\\ | &&&\\ | ||
Line 167: | Line 168: | ||
\hline | \hline | ||
&&&\\ | &&&\\ | ||
− | 3 & \frac{1}{4} \cdot \frac{1}{4} = \frac{1}{16} & \frac{1}{4} + \frac{1}{4} \cdot \frac{1}{4} = \frac{5}{16} & \frac{1}{4} \cdot \frac{1}{2} = \frac{ | + | 3 & \frac{1}{4} \cdot \frac{1}{4} = \frac{1}{16} & \frac{1}{4} + \frac{1}{4} \cdot \frac{1}{4} = \frac{5}{16} & \frac{1}{4} \cdot \frac{1}{2} + \frac{1}{2} = \frac{5}{8}\\ |
&&&\\ | &&&\\ | ||
\hline | \hline | ||
&&&\\ | &&&\\ | ||
− | + | 4 & \frac{5}{16} \cdot \frac{1}{4} = \frac{5}{64} & \frac{1}{16} + \frac{5}{16} \cdot \frac{1}{4} = \frac{9}{64} & \frac{5}{16} \cdot \frac{1}{2} + \frac{5}{8} = \frac{25}{32}\\ | |
&&&\\ | &&&\\ | ||
+ | \hline | ||
\end{array}</cmath> | \end{array}</cmath> | ||
− | <math>\frac{1}{2} + \frac{1}{ | + | Therefore, the answer is <math>\boxed{\textbf{(D)} ~\frac{25}{32}}</math>. |
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] | ||
+ | |||
+ | ==Solution 9== | ||
+ | Let us go through the frog’s jumps step by step to find the probability that it will land in a corner. Denote the frog’s position as <math>F</math>: | ||
+ | <asy> | ||
+ | label("$F$",(0,0)); draw((-1,-1)--(-1,1)--(1,1)--(1,-1)--cycle); draw((1,-1)--(1,1)--(3,1)--(3,-1)--cycle); draw((-1,1)--(-1,3)--(1,3)--(1,1)--cycle); draw((-3,-1)--(-3,1)--(-1,1)--(-1,-1)--cycle); draw((-1,-3)--(-1,-1)--(1,-1)--(1,-3)--cycle); draw((-3,-3)--(3,-3)--(3,3)--(-3,3)--cycle); | ||
+ | </asy> | ||
+ | First notice that since the frog only moves up, down, left or right, it’s original hop will not matter by symmetry, because all first hops will bring the frog at the edge next to two corners. WLOG we let the frog hop up: | ||
+ | <asy> | ||
+ | label("$F$",(0,2)); draw((-1,-1)--(-1,1)--(1,1)--(1,-1)--cycle); draw((1,-1)--(1,1)--(3,1)--(3,-1)--cycle); draw((-1,1)--(-1,3)--(1,3)--(1,1)--cycle); draw((-3,-1)--(-3,1)--(-1,1)--(-1,-1)--cycle); draw((-1,-3)--(-1,-1)--(1,-1)--(1,-3)--cycle); draw((-3,-3)--(3,-3)--(3,3)--(-3,3)--cycle); | ||
+ | </asy> | ||
+ | Notice that in its second hop, there are two ways for it to move to a corner (left and right) out of four, and thus the probability of Frieda reaching a corner on the second hop is <math>\frac{1}{2}</math>. | ||
+ | |||
+ | There are two other cases for Frieda’s second hop: it could either wrap around to another edge square or move back to the middle. We analyze each of these cases individually, noting that each has probability <math>\frac{1}{4}</math>: | ||
+ | <asy> | ||
+ | label("$F$",(0,-2)); draw((-1,-1)--(-1,1)--(1,1)--(1,-1)--cycle); draw((1,-1)--(1,1)--(3,1)--(3,-1)--cycle); draw((-1,1)--(-1,3)--(1,3)--(1,1)--cycle); draw((-3,-1)--(-3,1)--(-1,1)--(-1,-1)--cycle); draw((-1,-3)--(-1,-1)--(1,-1)--(1,-3)--cycle); draw((-3,-3)--(3,-3)--(3,3)--(-3,3)--cycle); | ||
+ | </asy> | ||
+ | In this case, there are again <math>2</math> choices to go to a corner on the third hop, go back to the previous square, or go to the middle. Here there is a <math>\frac{1}{2}</math> probability that Frieda will reach a corner on the third hop. If Frieda hops back with a <math>\frac{1}{4}</math> probability, she will again have a <math>\frac{1}{2}</math> chance of reaching a corner on her fourth hop, but after four hops she stops hopping, so there are no more chances for her to reach a corner if she hops back. If she hops to the middle, then her fourth hop cannot reach a corner and that case yields <math>0</math> probability of reaching a corner. | ||
+ | |||
+ | To sum up this case, the total probability of her reaching a corner is <math>\frac{1}{4}\left(\frac{1}{2}+\frac{1}{4}\cdot \frac{1}{2}\right)</math>. | ||
+ | |||
+ | Finally suppose Frieda goes back to her initial position after <math>2</math> steps. Then her third step again doesn’t matter because whatever she does, she will be next to <math>2</math> corners, so the probability of her reaching a corner on her fourth hop in this case is<math> \frac{1}{4}\cdot\frac{1}{2}</math>. | ||
− | ~ | + | Summing up all the cases, we get |
+ | <cmath>\frac{1}{2}+\frac{1}{4}\left(\frac{1}{2}+\frac{1}{4}\cdot\frac{1}{2}\right)+\frac{1}{4}\cdot\frac{1}{2} = \frac{1}{2}+\frac{1}{4}\left(\frac{1}{2}+\frac{1}{8}\right)+\frac{1}{8} = \frac{5}{4}\cdot\left(\frac{1}{2}+\frac{1}{8}\right) = \frac{5}{4} \cdot \frac{5}{8} = \boxed{\textbf{(D)} ~\frac{25}{32}}.</cmath> | ||
+ | ~KingRavi | ||
==Video Solution by Punxsutawney Phil== | ==Video Solution by Punxsutawney Phil== | ||
Line 183: | Line 210: | ||
== Video Solution by OmegaLearn (Using Probability States) == | == Video Solution by OmegaLearn (Using Probability States) == | ||
− | https://youtu.be/ | + | https://youtu.be/rLAcJe3o-uA?t=318 |
~ pi_is_3.14 | ~ pi_is_3.14 |
Latest revision as of 07:29, 4 November 2022
- The following problem is from both the 2021 AMC 10A #23 and 2021 AMC 12A #23, so both problems redirect to this page.
Contents
- 1 Problem
- 2 Solution 1 (Complementary Counting)
- 3 Solution 2 (Direct Counting and Probability States)
- 4 Solution 3 (Finds Numerator and Denominator Separately)
- 5 Solution 4
- 6 Solution 5
- 7 Solution 6 (Casework)
- 8 Solution 7
- 9 Solution 8 (Markov Chain)
- 10 Solution 9
- 11 Video Solution by Punxsutawney Phil
- 12 Video Solution by OmegaLearn (Using Probability States)
- 13 Video Solution by TheBeautyofMath
- 14 Video Solution by TheCALT (Casework)
- 15 Video Solution by MRENTHUSIASM (English & Chinese)
- 16 Video Solution by firebolt360
- 17 See also
Problem
Frieda the frog begins a sequence of hops on a grid of squares, moving one square on each hop and choosing at random the direction of each hop-up, down, left, or right. She does not hop diagonally. When the direction of a hop would take Frieda off the grid, she "wraps around" and jumps to the opposite edge. For example if Frieda begins in the center square and makes two hops "up", the first hop would place her in the top row middle square, and the second hop would cause Frieda to jump to the opposite edge, landing in the bottom row middle square. Suppose Frieda starts from the center square, makes at most four hops at random, and stops hopping if she lands on a corner square. What is the probability that she reaches a corner square on one of the four hops?
Solution 1 (Complementary Counting)
We will use complementary counting.
First, the frog can go left with probability . We observe symmetry, so our final answer will be multiplied by 4 for the 4 directions, and since
, we will ignore the leading probability.
From the left, she either goes left to another edge () or back to the center (
). Time for some casework.
She goes back to the center.
Now, she can go in any 4 directions, and then has 2 options from that edge. This gives . --End case 1
She goes to another edge (rightmost).
Subcase 1: She goes back to the left edge. She now has 2 places to go, giving
Subcase 2: She goes to the center. Now any move works.
for this case. --End case 2
She goes back to the center in Case 1 with probability , and to the right edge with probability
So, our answer is
But, don't forget complementary counting. So, we get . ~ firebolt360
Solution 2 (Direct Counting and Probability States)
We can draw a state diagram with three states: center, edge, and corner. Denote center by M, edge by E, and corner by C. There are a few ways Frieda can reach a corner in four or less moves: EC, EEC, EEEC, EMEC. Then, calculating the probabilities of each of these cases happening, we have , so the answer is
. ~IceWolf10
Solution 3 (Finds Numerator and Denominator Separately)
Suppose Frieda makes four independent hops without stopping so that each outcome is equally likely.
Denominator
There are ways for Frieda to make four hops without restrictions.
Numerator
We perform casework on which hop Frieda reaches a corner for the first time:
- The second hop (The third and the fourth hops have no restrictions.)
- The third hop (The fourth hop has no restrictions.)
- The fourth hop (There are two subcases based on the second hop.)
- The second hop "wraps around". It follows that the third hop must also "wrap around".
- The second hop returns to the center.
The four hops have options, respectively. So, this case has
ways.
No matter which direction the first hop takes, the second hop must "wrap around".
The four hops have options, respectively. So, this case has
ways.
The four hops have options, respectively. So, this subcase has
ways.
The four hops have options, respectively. So, this subcase has
ways.
Together, this case has ways.
The numerator is
Probability
The requested probability is
Remark
This problem is quite similar to 1995 AIME Problem 3.
~MRENTHUSIASM
Solution 4
Let be the probability that Frieda is on the central square after n moves,
be the probability that Frieda is on one of the four squares on the middle of the edges after n moves, and
(V for vertex) be the probability that Frieda is on a corner after n moves. The only way to reach the center is by moving in
specific direction out of
total directions from the middle of an edge, so
. The ways to reach the middle of an edge are by moving in any direction from the center or by moving in
specific direction from the middle of an edge, so
. The ways to reach a corner are by simply staying there after reaching there in a previous move or by moving in
specific directions from the middle of an edge, so
. Since Frieda always start from the center,
,
, and
. We use the previous formulas to work out
and find it to be
.
-SmileKat32
Solution 5
Imagine an infinite grid of by
squares such that there is a
by
square centered at
for all ordered pairs of integers
It is easy to see that the problem is equivalent to Frieda moving left, right, up, or down on this infinite grid starting at . (minus the teleportations) Since counting the complement set is easier, we'll count the number of
-step paths such that Frieda never reaches a corner point.
In other words, since the reachable corner points are and
Frieda can only travel along the collection of points included in
, where
is all points on
and
such that
and
, respectively, plus all points on the big square with side length
centered at
We then can proceed with casework:
Case : Frieda never reaches
nor
When Frieda only moves horizontally or vertically for her four moves, she can do so in ways for each case . Thus,
total paths for the subcase of staying in one direction. (For instance, all length
combinations of
and
except
,
,
, and
for the horizontal direction.)
There is another subcase where she changes directions during her path. There are four symmetric cases for this subcase depending on which of the four quadrants Frieda hugs. For the first quadrant, the possible paths are ,
,
, and
Thus, a total of
ways for this subcase.
Total for Case :
Case : Frieda reaches
or
.
Once Frieda reaches one of the points listed above (by using three moves), she has four choices for her last move. Thus, a total of paths for this case.
Our total number of paths never reaching coroners is thus making for an answer of
-fidgetboss_4000
Solution 6 (Casework)
We take cases on the number of hops needed to reach a corner. For simplicity, denote as a move that takes Frieda to an edge,
as wrap-around move and
as a corner move. Also, denote
as a move that takes us to the center.
2 Hops
Then, Frieda will have to as her set of moves. There are
ways to move to an edge, and
corners to move to, for a total of
cases here. Then, there are
choices for each move, for a probability of
.
3 Hops
In this case, Frieda must wrap-around. There's only one possible combination, just . There are
ways to move to an edge,
way to wrap-around (you must continue in the same direction) and
corners, for a total of
cases here. Then, there are
choices for each move, for a probability of
.
4 Hops
Lastly, there are two cases we must consider here. The first case is , and the second is
. For the first case, there are
ways to move to an edge,
way to return to the center,
ways to move to an edge once again, and
ways to move to a corner. Hence, there is a total of
cases here. Then, for the second case, there are
ways to move to a corner,
way to wrap-around,
way to wrap-around again, and
ways to move to a corner. This implies there are
cases here. Then, there is a total of
cases, out of a total of
cases, for a probability of
.
Then, the total probability that Frieda ends up on a corner is , corresponding to choice
. ~rocketsri
Solution 7
I denote 3x3 grid by
- HOME square (x1)
- CORN squares (x4)
- SIDE squares (x4)
Transitions:
- HOME always move to SIDE
- CORN is DONE
- SIDE move to HOME with move to SIDE with
and move to CORN with
After one move, will be on square
After two moves, will be
After three moves, will be
After four moves, probability on CORN will be
~ ccx09
Solution 8 (Markov Chain)
The grid is symmetrical. Denote the center cell as state Center, the middle side cells as state Side, the
corner cells as state Corner. We can draw the following State Transition Diagram with Markov Chain. The numbers on the transition arc are the transition probability.
We calculate the probability of different states in each round in the following table by iterating a few more times:
Therefore, the answer is .
Solution 9
Let us go through the frog’s jumps step by step to find the probability that it will land in a corner. Denote the frog’s position as :
First notice that since the frog only moves up, down, left or right, it’s original hop will not matter by symmetry, because all first hops will bring the frog at the edge next to two corners. WLOG we let the frog hop up:
Notice that in its second hop, there are two ways for it to move to a corner (left and right) out of four, and thus the probability of Frieda reaching a corner on the second hop is
.
There are two other cases for Frieda’s second hop: it could either wrap around to another edge square or move back to the middle. We analyze each of these cases individually, noting that each has probability :
In this case, there are again
choices to go to a corner on the third hop, go back to the previous square, or go to the middle. Here there is a
probability that Frieda will reach a corner on the third hop. If Frieda hops back with a
probability, she will again have a
chance of reaching a corner on her fourth hop, but after four hops she stops hopping, so there are no more chances for her to reach a corner if she hops back. If she hops to the middle, then her fourth hop cannot reach a corner and that case yields
probability of reaching a corner.
To sum up this case, the total probability of her reaching a corner is .
Finally suppose Frieda goes back to her initial position after steps. Then her third step again doesn’t matter because whatever she does, she will be next to
corners, so the probability of her reaching a corner on her fourth hop in this case is
.
Summing up all the cases, we get
~KingRavi
Video Solution by Punxsutawney Phil
https://youtube.com/watch?v=kHLR57iP0cU
Video Solution by OmegaLearn (Using Probability States)
https://youtu.be/rLAcJe3o-uA?t=318
~ pi_is_3.14
Video Solution by TheBeautyofMath
~IceMatrix
Video Solution by TheCALT (Casework)
https://www.youtube.com/watch?v=BHHZPy9VjAM
~bobthegod78
Video Solution by MRENTHUSIASM (English & Chinese)
https://www.youtube.com/watch?v=f6LrMimIUWw
~MRENTHUSIASM
Video Solution by firebolt360
~firebolt360
See also
2021 AMC 10A (Problems • Answer Key • Resources) | ||
Preceded by Problem 22 |
Followed by Problem 24 | |
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 10 Problems and Solutions |
2021 AMC 12A (Problems • Answer Key • Resources) | |
Preceded by Problem 22 |
Followed by Problem 24 |
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.