2021 AMC 12B Fall Problem 17

Question

A bug starts at a vertex of a grid made of equilateral triangles of side length

1.

At each step the bug moves in one of the

6

possible directions along the grid lines randomly and independently with equal probability. What is the probability that after

5

moves the bug never will have been more than

1

unit away from the starting position?

\dfrac{13}{108}

\dfrac{7}{54}

\dfrac{29}{216}

\dfrac{4}{27}

\dfrac{1}{16}

The bug must always be at the start or one of its

6

neighbors

From a neighbor, only

3

of the

6

moves stay within distance

1

: back to start or to the two adjacent neighbors

Staying within distance

1

means the bug is always at the origin or one of its

6

neighbors. From the origin, all

6

moves are allowed. From a neighbor, only

3

moves keep it in range: back to the origin, or to either of the two adjacent neighbors.

Let

a_k

and

b_k

count valid

k

-step paths ending at the origin and at a neighbor. Then

a_{k+1} = b_k

and

b_{k+1} = 6a_k + 2b_k,

starting from

a_0 = 1,

b_0 = 0.

Iterating gives

b_1 = 6,

then

(a_2, b_2) = (6, 12),

(a_3, b_3) = (12, 60),

(a_4, b_4) = (60, 192),

(a_5, b_5) = (192, 744).

The total number of valid paths is

192 + 744 = 936.

The probability is

\dfrac{936}{6^5} = \dfrac{936}{7776} = \dfrac{13}{108}.

Thus, the correct answer is A.

Problem 17 in other years