jmc

Question

A bug starts at a vertex of an equilateral triangle. On each move, it randomly selects one of the two vertices where it is not currently located, and crawls along a side of the triangle to that vertex. Given that the probability that the bug moves to its starting vertex on its tenth move is m/n, where m and n are relatively prime positive integers, find m + n.

Accepted Answer

Let P_n represent the probability that the bug is at its starting vertex after n moves. If the bug is on its starting vertex after n moves, then it must be not on its starting vertex after n-1 moves. At this point it has 12 chance of reaching the starting vertex in the next move. Thus P_n=12(1-P_n-1). P_0=1, so now we can build it up: P_1=0, P_2=12, P_3=14, P_4=38, P_5=516, P_6=1132, P_7=2164, P_8=43128, P_9=85256, P_10=171512, Thus the answer is 171+512=683