Problem:
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.
Solution:
If the bug is at the starting vertex after move n, the probability is 1 that it will move to a non-starting vertex on move n+1. If the bug is not at the starting vertex after move n, the probability is 1/2 that it will move back to its starting vertex on move n+1, and the probability is 1/2 that it will move to another nonstarting starting vertex on move n+1. Let pn be the probability that the bug isat the starting vertex after move n. Then pn+1=0⋅pn+21(1−pn)=−21pn+21. This implies that pn+1−31=−21(pn−31). Since p0−31=1−31=2/3, conclude that pn−31=32⋅(−21)n. Therefore
pn=32⋅(−21)n+31=31+(−1)n2n−11=3⋅2n−12n−1+(−1)n
Substitute 10 for n to find that p10=171/512, and m+n is 683 .
OR
A 10-step path can be represented by a 10-letter sequence consisting of only A 's and B 's, where A represents a move in the clockwise direction and B represents a move in the counterclockwise direction. Where the path ends depends on the number of A 's and B 's, not on their arrangement. Let x be the number of A 's, and let y be the number of B 's. Note that the bug will be home if and only if x−y is a multiple of 3 . After 10 moves, x+y=10. Then 2x=10+3k for some integer k, and so x=5+3j for some integer j. Thus the number of A 's must be 2,5 , or 8 , and the desired probability is
210(210)+(510)+(810)=512171
OR
Let X be the bug's starting vertex, and let Y and Z be the other two vertices. Let xk,yk, and zk be the probabilities that the bug is at vertex X,Y, and Z, respectively, at move k, for k≥0. Then xk+1=.5yk+.5zk,yk+1=.5xk+.5zk, and zk+1=.5xk+.5yk. This can be written as
⎣⎢⎡xk+1yk+1zk+1⎦⎥⎤=⎣⎢⎡0.5.5.50.5.5.50⎦⎥⎤⎣⎢⎡xkykzk⎦⎥⎤
Thus
⎣⎢⎡x10y10z10⎦⎥⎤=⎣⎢⎡0.5.5.50.5.5.50⎦⎥⎤10⎣⎢⎡100⎦⎥⎤
and x10=171/512.
The problems on this page are the property of the MAA's American Mathematics Competitions