2021 Fall AMC 12B Problems/Problem 17
Contents
Problem
A bug starts at a vertex of a grid made of equilateral triangles of side length . At each step the bug moves in one of the possible directions along the grid lines randomly and independently with equal probability. What is the probability that after moves the bug never will have been more than unit away from the starting position?
Solution 1 (Recursion)
Let be the number of paths of moves such that the bug never will have been more than unit away from the starting position. Clearly, by symmetry, there are two possible states here, the bug being on the center and the bug being on one of the vertices of the unit hexagon around the center. Let be the number of paths with the aforementioned restriction that end on the center. Let be the number of paths with the aforementioned restriction that end on a vertex of the surrounding unit hexagon. We have since from the center, there are possible points to land to and from a vertex there are possible points to land to (the two adjacent vertices and the center). We also have , since to get to the center the bug must have come from a vertex, and since from a vertex there are two vertices to move to, and from the center there are vertices to move to. We can construct a recursion table using the base cases and and our recursive rules for and as follows: Then, and the desired probability is thus
~fidgetboss_4000
Solution 2 (Recursion)
Let be such probability after moves. , . Then, . Then, we can prove the recursive formula Now, we evaluate .
Solution 3 (Recursion)
We use to denote the bug's current state. We wish to find .
The first argument denotes the bug's current position. We use to denote the bug's starting point. We use to denote any point whose distance to the bug's starting point is .
The second argument denotes the remaining number of moves the bug has.
For and , we have For and , we have For and , we have We solve this recursive equation by using backward induction: Therefore, the answer is .
~Steven Chen (www.professorchenedu.com)
Solution 4 (Generating Function)
Use a generating function, define be ways for the destination be units away from the origin.
We conclude that:
 If the current point is origin, then we need to multiply by .
 If the current point on vertex of the unit hexagon, then we need to multiply by , where there is way to return to the origin and there are two ways to keep distance .
Now let's start with .
st step:
nd step:
rd step:
th step:
th step:
So, there are ways for the bug never moves more than unit away from origin. The answer is .
~wwei.yu
Solution 5 (Casework)
In the following diagram, let denote the vertex where the bug starts (shown in red) and denote one of the adjacent vertices (shown in green). Note that:
 If the bug is at then the probability that it moves to next is
 If the bug is at then the probability that it moves to next is
 If the bug is at then the probability that it moves to next is
We apply casework to the possible paths of the bug:

The probability for this case is

The probability for this case is

The probability for this case is

The probability for this case is

The probability for this case is

The probability for this case is

The probability for this case is

The probability for this case is
Together, the answer is ~MRENTHUSIASM
See Also
2021 Fall AMC 12B (Problems • Answer Key • Resources)  
Preceded by Problem 16 
Followed by Problem 18 
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.