2005 AMC 12B Problems/Problem 25
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?
We approach this problem by counting the number of ways ants can do their desired migration, and then multiple this number by the probability that each case occurs.
Let the octahedron be , with points coplanar. Then the ant from and the ant from must move to plane . Suppose, without loss of generality, that the ant from moved to point . Then, we must consider three cases.
- Case 1: Ant from point moved to point
On the plane, points and are taken. The ant that moves to can come from either or . The ant that moves to can come from either or . Once these two ants are fixed, the other two ants must migrate to the "poles" of the octahedron, points and . Thus, there are two degrees of freedom in deciding which ant moves to , two degrees of freedom in deciding which ant moves to , and two degrees of freedom in deciding which ant moves to . Hence, there are ways the ants can move to different points.
- Case 2: Ant from point moved to point
On the plane, points and are taken. The ant that moves to must be from or , but the ant that moves to must also be from or . The other two ants, originating from points and , must move to the poles. Therefore, there are two degrees of freedom in deciding which ant moves to and two degrees of freedom in choosing which ant moves to . Hence, there are ways the ants can move to different points.
- Case 3: Ant from point moved to point
By symmetry to Case 1, there are ways the ants can move to different points.
Given a point , there is a total of ways the ants can move to different points. We oriented the square so that point was defined as the point to which the ant from point moved. Since the ant from point can actually move to four different points, there is a total of ways the ants can move to different points.
Each ant acts independently, having four different points to choose from. Hence, each ant has probability of moving to the desired location. Since there are six ants, the probability of each case occuring is . Thus, the desired answer is .
Let be the number of cycles of length the can be walked among the vertices of an octahedron. For example, would represent the number of ways in which an ant could navigate vertices and then return back to the original spot. Since an ant cannot stay still, . We also easily see that .
Now consider any four vertices of the octahedron. All four vertices will be connected by edges except for one pair. Let’s think of this as a square with one diagonal (from top left to bottom right). EDIT: This part is wrong as if you choose the 4 vertices that have a cross section as a square, there exists no connecting diagonal.
Suppose an ant moved across this diagonal; then the ant at the other end can only move across the diagonal (which creates 2-cycle, bad) or it can move to another vertex, but then the ant at that vertex must move to the spot of the original ant (which creates 3-cycle, bad). Thus none of the ants can navigate the diagonal and can either shift clockwise or counterclockwise, and so .
For , consider an ant at the top of the octahedron. It has four choices. Afterwards, it can either travel directly to the bottom, and then it has ways back up, or it can travel along the sides and then go to the bottom, of which simple counting gives us ways back up. Hence, this totals .
Now, the number of possible ways is given by the sum of all possible cycles,
where the coefficients represent the number of ways we can configure these cycles. To find , fix any face, there are adjacent faces to select from to complete the cycle. From the four remaining faces there are only ways to create cycles, hence .
To find , each cycle of faces is distinguished by their common edge, and there are edges, so .
To find , each three-cycle is distinguished by the vertex, and there are edges. However, since the two three-cycles are indistinguishable, .
Clearly . Finally,
Each bug has possibilities to choose from, so the probability is .
We use the idea of cycles.
Case 1: Two 3-cycles. We have 4 ways to divide the faces into cycles. There are 8 faces, and once a face has been chosen, the other three vertices must form the other cycle of length 3. Then there are ways to choose the direction of the cycle. There are
Case 2: Three 2-cycles. There are ways to do so.
Case 3: One 4-cycle, one 2-cycle. There are ways here because there are 12 different edges for the 2-cycle and we can choose the direction of the 4-cycle.
Case 4: One 6-cycle. Visualizing the octahedron as a 4-sided pyramid pointing up above one pointing down, we look at the ways an ant can start from the top vertex and visit all vertices without revisiting one along the way and returning to the top. Because the first step must be from the top to the middle square ring, we choose one vertex to move to and will multiply the final result by four.
We divide the paths into two sub-cases.
Sub-case 1: The ant continues to the bottom vertex. In this case, the ant has visited three corners of a square, but can not next visit the fourth corner or there will be no way to connect the remaining two vertices of the octahedron. Thus, the ant must next visit one of the other two vertices, and that selection decides the remainder of the path. Thus, this sub-case has 2 possible paths.
Sub-case 2: The ant continues along the "equator" square ring. By symmetry, there are two choices. Choose one, and we will multiply the final result by two. From that second point on the equator, there are two choices. If it continues to a third point on the equator, there is only one path to complete the cycle. If it next moves to the bottom vertex, there are two ways to complete the cycle. This gives a total of three possible paths. Multiplying by 2 gives 6 for this sub-case.
There are ways here.
Overall, there are cases. Answer is
~Williamgolly + Dr. 17
|2005 AMC 12B (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25|
|All AMC 12 Problems and Solutions|