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}$

Answer: A

Concepts:random walk recursive probability

Difficulty rating: 2230

Solution:

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.

2021 AMC 12B Fall Problem 17

Answer: A

Difficulty rating: 2230

Solution:

Problem 17 in Other Years