2021 Fall AMC 12B Problems/Problem 17
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
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
We use to denote the bug's current state.
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 1.
The second argument denotes the remaining number of moves the bug has.
For and
,
For and
,
For and
,
We solve this recursive equation by using backward induction.
We get
and
and
and
and
Therefore, the answer is .
~Steven Chen (www.professorchenedu.com)
Solution 3 (Generating function)
Use generating function, define be
ways for the end point be
unit away from the origins.
Therefore,
if the current point is origin, need to
if the current point on vertex of the unit hexagon, need to , where there is one way to return to the origin and there are two ways to keep distance = 1
Now let's start with ;
1st step:
2nd step:
3rd step:
4th step:
5th step:
So there are ways for the bug never moves more than 1 unit away from orign, and
-wwei.yu