Question

Let $A,$ $B,$ $C,$ and $D$ be the vertices of a regular tetrahedron, each of whose edges measures $1$ meter. A bug, starting from vertex $A,$ observes the following rule: at each vertex it chooses one of the three edges meeting at that vertex, each edge being equally likely to be chosen, and crawls along that edge to the vertex at its opposite end. Let $p=\frac{n}{729}$ be the probability that the bug is at vertex $A$ when it has crawled exactly $7$ meters. Find the value of $n.$

Answer

Answer: 182

Concepts:random walk recursion basic probability

Difficulty rating: 2260

Small Hint:

Let $p_k$ be the probability of being at $A$ after $k$ steps

Big Hint:

From any vertex other than $A,$ the probability of moving to $A$ is $\frac{1}{3}$

Solution:

Let $p_k$ be the probability that the bug is at $A$ after $k$ steps. It cannot stay at $A,$ while from any other vertex it moves to $A$ with probability $\frac{1}{3}.$ Hence $p_{k+1}=\frac{1-p_k}{3},\qquad p_0=1.$ Solving this recurrence gives $p_k=\frac14+\frac34\left(-\frac13\right)^k.$ Thus $p_7=\frac14-\frac{3}{4\cdot3^7}=\frac{182}{729},$ so $n=182.$

1985 AIME Problem 12

Answer: 182

Difficulty rating: 2260

Small Hint:

Big Hint:

Solution:

Problem 12 in Other Years