Problem:
Six ants simultaneously stand on the six vertices of a regular octahedron, with each ant at a different vertex. Simultaneously and independently, each ant moves from its vertex to one of the four adjacent vertices, each with equal probability. What is the probability that no two ants arrive at the same vertex?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
Because each ant can move from its vertex to any of four adjacent vertices, there are possible combinations of moves. In the following, consider only those combinations in which no two ants arrive at the same vertex. Label the vertices as and , where and are opposite and , respectively. Let be the function that maps each ant's starting vertex onto its final vertex. Then neither of nor can be either or , and similar statements hold for the other pairs of opposite vertices. Thus there are ordered pairs of values for and . The vertices and are opposite each other in four cases and adjacent to each other in eight.
Suppose that and are opposite vertices, and, without loss of generality, that and . Then must be either or and must be the other. Similarly, must be either or and must be the other. Therefore there are combinations of moves in which and are opposite each other.
Suppose now that and are adjacent vertices, and, without loss of generality, that and . Then one of and must be and the other cannot be . So there are four possible ordered pairs of values for and . For each of those there are two possible ordered pairs of values for and . Therefore there are combinations of moves in which and are adjacent to each other.
Hence the probability that no two ants arrive at the same vertex is
The problems on this page are the property of the MAA's American Mathematics Competitions