2022 AMC 8 Problems/Problem 25
Contents
Problem
A cricket randomly hops between leaves, on each turn hopping to one of the other leaves with equal probability. After hops what is the probability that the cricket has returned to the leaf where it started?
Solution 1 (Casework)
Let denote the leaf where the cricket starts and denote one of the other leaves. Note that:
- If the cricket is at then the probability that it hops to next is
- If the cricket is at then the probability that it hops to next is
- If the cricket is at then the probability that it hops to next is
We apply casework to the possible paths of the cricket:
-
The probability for this case is
-
The probability for this case is
Together, the probability that the cricket returns to after hops is
~MRENTHUSIASM
Solution 2 (Casework)
We can label the leaves as shown below:
Carefully counting cases, we see that there are ways for the cricket to return to leaf after four hops if its first hop was to leaf :
By symmetry, we know that there are ways if the cricket's first hop was to leaf , and there are ways if the cricket's first hop was to leaf . So, there are ways in total for the cricket to return to leaf after four hops.
Since there are possible ways altogether for the cricket to hop to any other leaf four times, the answer is .
~mahaler
Solution 3 (Recursion)
Denote to be the probability that the cricket would return back to the first point after hops. Then, we get the recursive formula because if the leaf is not on the target leaf, then there is a probability that it will make it back.
With this formula and the fact that (After one hop, the cricket can never be back to the target leaf.), we have so our answer is .
~wamofan
Solution 4 (Dynamic Programming)
Let denote the leaf cricket starts at, and be the other leaves, similar to Solution 2.
Let be the probability the cricket lands on after hops, be the probability the cricket lands on after crawling hops, and etc.
Note that and For the probability that the cricket land on each leaf after hops is the sum of the probability the cricket land on other leaves after hops. So, we have It follows that
We construct the following table: Therefore, the answer is .
Solution 5 (Generating Function)
Assign the leaves to and modulo and let be the starting leaf. We then use generating functions with relation to the change of leaves. For example, from to would be a change of and from to would be a change of This generating function is equal to It is clear that we want the coefficients in the form of where is a positive integer. One application of roots of unity filter gives us a successful case count of
Therefore, the answer is
~sigma
Solution 6 (Casework)
Let be the leaf where the cricket was originally on. Note that the 3rd hop cannot be on .
We form 2 cases.
Case 1: The cricket hops on the 3 leaves that don't include for the 1st, 2nd, and 3rd hop.
There are choices for the 1st hop, for the 2nd, for the 3rd, and for the 4th (the cricket has to return). In total, .
Case 2: The cricket returns to on the 2nd hop.
There are choices for the 1st hop, for the 2nd (it has to return), for the 3rd, and for the 4th. We get .
Since there are a total of paths, the probability is .
~MrThinker
Remark
This problem is a reduced version of 1985 AIME Problem 12, changing steps into steps.
This problem is also similar to 2003 AIME II Problem 13.
Video Solution
https://www.youtube.com/watch?v=85A6av3oqRo
~Mathematical Dexterity
Video Solution
https://youtu.be/Ij9pAy6tQSg?t=2588
~Interstigation
Video Solution
https://www.youtube.com/watch?v=H1zxrkq6DKg
Video Solution
https://youtu.be/0orAAUaLIO0?t=609
~STEMbreezy
See Also
2022 AMC 8 (Problems • Answer Key • Resources) | ||
Preceded by Problem 24 |
Followed by Last Problem | |
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 AJHSME/AMC 8 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.