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

Revision as of 21:39, 23 February 2009

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}$ .

Revision as of 21:37, 23 February 2009 (view source) Jtanman (talk \| contribs) (→‎Solution 1) ← Older edit		Revision as of 21:39, 23 February 2009 (view source) Jtanman (talk \| contribs) (→‎Solution 1) Newer edit →
Line 18:		Line 18:

	*Case 1: Ant from point <math>F</math> moved to point <math>C</math>		*Case 1: Ant from point <math>F</math> moved to point <math>C</math>
−	On the plane, points <math>B</math> and <math>C</math> are taken. The ant that moves to D can come from either <math>E</math> or <math>C</math>. The ant that moves to <math>E</math> can come from either <math>B</math> or <math>D</math>. Once these two ants are fixed, the other two ants must migrate to the "poles" of the octahedron, points <math>A</math> and <math>F</math>. Thus, there are two degrees of freedom in deciding which ant moves to <math>D</math>, two degrees of freedom in deciding which ant moves to <math>C</math>, and two degrees of freedom in deciding which ant moves to <math>A</math>. Hence, there are <math>2 \times 2 \times 2=8</math> ways the ants can move to different points.	+	On the plane, points <math>B</math> and <math>C</math> are taken. The ant that moves to D can come from either <math>E</math> or <math>C</math>. The ant that moves to <math>E</math> can come from either <math>B</math> or <math>D</math>. Once these two ants are fixed, the other two ants must migrate to the "poles" of the octahedron, points <math>A</math> and <math>F</math>. Thus, there are two degrees of freedom in deciding which ant moves to <math>D</math>, two degrees of freedom in deciding which ant moves to <math>E</math>, and two degrees of freedom in deciding which ant moves to <math>A</math>. Hence, there are <math>2 \times 2 \times 2=8</math> ways the ants can move to different points.

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