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​)=−21​pn​+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+1​yk+1​zk+1​​⎦⎥⎤​=⎣⎢⎡​0.5.5.50.5.5.50​⎦⎥⎤​⎣⎢⎡​xk​yk​zk​​⎦⎥⎤​
Thus
⎣⎢⎡​x10​y10​z10​​⎦⎥⎤​=⎣⎢⎡​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