Problem:
An ant makes a sequence of moves on a cube where a move consists of walking from one vertex to an adjacent vertex along an edge of the cube. Initially the ant is at a vertex of the bottom face of the cube and chooses one of the three adjacent vertices to move to as its first move. For all moves after the first move, the ant does not return to its previous vertex, but chooses to move to one of the other two adjacent vertices. All choices are selected at random so that each of the possible moves is equally likely. The probability that after exactly moves that ant is at a vertex of the top face on the cube is , where and are relatively prime positive integers.
Find .
Solution:
We define to represent the probability that, after total moves, the ant ends up on the same level (top or bottom) it started on — namely, the bottom face.
The ant begins at a vertex on the bottom face of a cube. On the first move, it can move to adjacent vertices: of those are on the bottom face, and is on the top face. Since it chooses uniformly at random, the chance it remains on the bottom face after move is . For the sake of the recurrence, we use a different perspective and define , analyzing transitions from future states instead.
Now observe the ant's behavior for . At move , the ant either:
stays on the same level, with probability , coming from the same level at move ; or
it switches from the opposite level, with probability , having come from move .
This leads to the recurrence: with base cases , .
Now compute:
To return to the original setup, where the ant starts on the bottom face and makes moves, we compute:
Thus, the final answer is .
The problems on this page are the property of the MAA's American Mathematics Competitions