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 8 moves that ant is at a vertex of the top face on the cube is nm, where m and n are relatively prime positive integers.
Find m+n.
Solution:
Answer (049):
Denote moves between the bottom face and the top face by V (vertical moves) and other moves by H (horizontal moves). Then every sequence of moves can be written as a sequence of Vs and Hs, for example, HVHHHVHV. The probabilities that the first move is H or V are 32 and 31, respectively. The probabilities that the next move after an H is H or V are both 21. The probability that the next move after a V is H is 1 . The problem requests the probability that the number of V moves in a sequence of eight moves is odd, which happens when there are either 1 or 3 vertical moves.
- Suppose there is 1 V in the sequence. If V is the first move, the probability is 31⋅1⋅(21)6=3⋅261. If V is the last move, the probability is 32⋅(21)7=3⋅261. Otherwise, the probability is 6⋅32⋅1⋅(21)6=241.
- Suppose there are 3 Vs in the sequence. If the first and last moves are V , the probability is 4⋅31⋅12⋅(21)5=3⋅231. If the first move is V and the last move is H , the probability is (24)⋅31⋅13⋅(21)4=231. If the first move is H and the last move is V , the probability is (24)⋅32⋅12⋅(21)5=231. If V is neither first nor last, the probability is 4⋅32⋅13⋅(21)4=3⋅21.
The required probability is
3⋅261+3⋅261+241+3⋅231+231+231+3⋅21=3217
The requested sum is 17+32=49.
OR
Define V and H as above. Immediately after a horizontal move is made, let an be the probability that the ant will be on the same face (top or bottom) at the beginning and the end of n more moves. If the following move is H , then the ant ends up on the same face in n additional moves after this H with probability an. If the following move is V , then the ant ends up on the same face in n additional moves after this V with probability 1−an−1. Because P(H)=P(VH)=21 following a horizontal move, it follows that for n>2
an=21an−1+21(1−an−2).
Because a1=P(H)=21 and a2=P(HH)=41, it follows that a3=83,a4=169,a5=3219,a6=6433, and a7=12859. Finally, because at the outset P(H)=32 and P(VH)=31, the ant is on the bottom face after eight moves with probability
32a7+31(1−a6)=3215.
Thus the ant is on the top face with probability 1−3215=3217, as above.
OR
For each n=1,…,8, let an,bn,xn, and yn denote the number of paths of length n whose last move stays on the top face, moves from top to bottom, stays on the bottom face, or moves from bottom to top, respectively. Then the following recursions hold for n≥2 :
anbnxnyn=an−1+2yn−1=an−1=xn−1+2bn−1=xn−1.
The number of paths can be computed recursively yielding
| Last move |
n |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
| Stay on top |
an |
0 |
2 |
6 |
10 |
14 |
26 |
62 |
138 |
| Move to bottom |
bn |
0 |
0 |
2 |
6 |
10 |
14 |
26 |
62 |
| Stay on bottom |
xn |
2 |
2 |
2 |
6 |
18 |
38 |
66 |
118 |
| Move to top |
yn |
1 |
2 |
2 |
2 |
6 |
18 |
38 |
66 |
In general the nth column sums to 3⋅2n−1, so the required probability is
3⋅27a8+y8=384138+66=3217,
as above.
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions