Difference between revisions of "2005 AMC 12B Problems/Problem 25"

Revision as of 18:53, 24 June 2021

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?

$\mathrm{(A)}\ \frac {5}{256} \qquad\mathrm{(B)}\ \frac {21}{1024} \qquad\mathrm{(C)}\ \frac {11}{512} \qquad\mathrm{(D)}\ \frac {23}{1024} \qquad\mathrm{(E)}\ \frac {3}{128}$

Solution

Solution 1

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 $ABCDEF$ , with points $B,C,D,E$ coplanar. Then the ant from $A$ and the ant from $F$ must move to plane $BCDE$ . Suppose, without loss of generality, that the ant from $A$ moved to point $B$ . Then, we must consider three cases.

Case 1: Ant from point $F$ moved to point $C$

On the plane, points $B$ and $C$ are taken. The ant that moves to $D$ can come from either $E$ or $C$ . The ant that moves to $E$ can come from either $B$ or $D$ . Once these two ants are fixed, the other two ants must migrate to the "poles" of the octahedron, points $A$ and $F$ . Thus, there are two degrees of freedom in deciding which ant moves to $D$ , two degrees of freedom in deciding which ant moves to $E$ , and two degrees of freedom in deciding which ant moves to $A$ . Hence, there are $2 \times 2 \times 2=8$ ways the ants can move to different points.

Case 2: Ant from point $F$ moved to point $D$

On the plane, points $B$ and $D$ are taken. The ant that moves to $C$ must be from $B$ or $D$ , but the ant that moves to $E$ must also be from $B$ or $D$ . The other two ants, originating from points $C$ and $E$ , must move to the poles. Therefore, there are two degrees of freedom in deciding which ant moves to $C$ and two degrees of freedom in choosing which ant moves to $A$ . Hence, there are $2 \times 2=4$ ways the ants can move to different points.

Case 3: Ant from point $F$ moved to point $E$

By symmetry to Case 1, there are $8$ ways the ants can move to different points.

Given a point $B$ , there is a total of $8+4+8=20$ ways the ants can move to different points. We oriented the square so that point $B$ was defined as the point to which the ant from point $A$ moved. Since the ant from point $A$ can actually move to four different points, there is a total of $4 \times 20=80$ ways the ants can move to different points.

Each ant acts independently, having four different points to choose from. Hence, each ant has probability $1/4$ of moving to the desired location. Since there are six ants, the probability of each case occuring is $\frac{1}{4^6} = \frac{1}{4096}$ . Thus, the desired answer is $\frac{80}{4096}= \boxed{\frac{5}{256}} \Rightarrow \mathrm{(A)}$ .

Solution 2

Let $f(n)$ be the number of cycles of length $n$ the can be walked among the vertices of an octahedron. For example, $f(3)$ would represent the number of ways in which an ant could navigate $2$ vertices and then return back to the original spot. Since an ant cannot stay still, $f(1) = 0$ . We also easily see that $f(2) = 1, f(3) = 2$ .

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).

$[asy] size(30); defaultpen(0.6); pair A = (0,0), B=(5,0), C=(5,5), D=(0,5); draw(A--B--C--D--cycle); draw(B--D); [/asy]$

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 $f(4) = 2$ .

For $f(6)$ , 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 $2$ ways back up, or it can travel along the sides and then go to the bottom, of which simple counting gives us $6$ ways back up. Hence, this totals $4 \times (2+6) = 32$ .

Now, the number of possible ways is given by the sum of all possible cycles, $a \cdot f(2) \cdot f(2) \cdot f(2) + b \cdot f(2) \cdot f(4) + c \cdot f(3) \cdot f(3) + d \cdot f(6)$

where the coefficients represent the number of ways we can configure these cycles. To find $a$ , fix any face, there are $4$ adjacent faces to select from to complete the cycle. From the four remaining faces there are only $2$ ways to create cycles, hence $a = 8$ .

To find $b$ , each cycle of $2$ faces is distinguished by their common edge, and there are $12$ edges, so $b = 12$ .

To find $c$ , each three-cycle is distinguished by the vertex, and there are $8$ edges. However, since the two three-cycles are indistinguishable, $c = 8/2 = 4$ .

Clearly $d = 1$ . Finally,

$8(1)(1)(1) + 12(1)(2) + 4(2)(2) + (32) = 80$

Each bug has $4$ possibilities to choose from, so the probability is $\frac{80}{4^6} = \frac{5}{256}$ .

Solution 3

We use the idea of cycles.

Case 1: 2 3-cycles. We have 4 ways to divide the faces into cycles (do casework on which two ants share a cycle with ant A), then $2^2$ ways to choose the direction of the cycle. There are $4 \cdot 4 = 16.$

Case 2: 3 2-cycles. There are $4 \cdot 2 = 8$ ways to do so.

Case 3: 1 4-cycle, 1 2-cycle. There are $12 \cdot 2 = 24$ ways here because there are 12 different edges for the 2-cycle and we can choose the direction of the 4-cycle.

Case 4: 1 6-cycle. There are $4 \cdot 2 = 8$ ways here because we do casework on which place the ant A goes and which ant goes to vertex A (which is at the top).

Overall, there are $40$ cases. Answer is $40/2^{12} = 5/256$

~Williamgolly

2005 AMC 12B (Problems • Answer Key • Resources)
Preceded by Problem 24	Followed by Last question
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

Page

Toolbox

Search