## Wednesday, November 30, 2005

### Can you count? Topic: Probability. Level: AMC/AIME.

Problem: (2005 AMC 12B - #25) Six ants are on the vertices of a regular octahedron - one on each vertex. Simultaneous and independently, they each traverse one edge and arrive at another vertex. What is the probability that no two ants arrive at the same vertex?

Solution: We wish to count the number of ways the ants can move such that no two arrive at the same vertex. Consider viewing the octahedron as two points with a square between them such that the square is perpendicular to the line containing the two points. Note that two of the ants on the square must move off and the two off the square must move on.
-----
CASE 1: Two ants opposite each other on the square move off.

There are two possible pairs of ants and each pair has two ways of moving off (each one can go to either point off the square). That's $4$ possibilities.

Now consider the remaining two ants on the square. There are two ways they can move such that they don't arrive at the same vertex. That's $2$ possibilities.

Now consider the two ants off the square. There are two ways they can move onto the square (each can go to either open point). That's $2$ possibilities.

So we have $4 \cdot 2 \cdot 2 = 16$ possibilities for the first case.
-----
CASE 2: Two ants adjacent to each other on the square move off.

There are four pairs of ants adjacent to each other on the square. Each pair can move off in two different ways (same argument as CASE 1). That's $8$ possibilities.

The remaining two ants can move anywhere on the square and not be at the same vertex, giving $4$ possibilities.

The two ants off the square can move onto the square in two different ways (same argument as CASE 1). That's $2$ possibilities.

So we have $8 \cdot 4\cdot 2 = 64$ possibilites for the second case.
-----
Now consider the total possible ways satisfying the condition: $16+64 = 80$. And the total number of ways the ants can move $4^6$ (each ant has $4$ places it can go). Thus our desired probability is

$\frac{80}{4^6} = \frac{5}{256}$.

--------------------

Comment: Admittedly, the problem does look daunting when encountered at the end of the AMC-12, in your final minutes of the test, and I did not try very hard to solve the problem at the time, either. However, once you find a relatively simple method to analyze the number of ways (viewing it as two points and a square - consider the possible pairs on the square), the real counting process is quite simple. And the problem seems to just finish itself.

--------------------

Practice Problem #1: Repeat the problem above, but use a tetrahedron instead of an octahedron.

Practice Problem #2: Consider a regular hexagon with all its diagonals drawn in. What is the probability that, given any two of the seven points (including the center - intersection of the diagonals), the line segment between the points is drawn?

Practice Problem #3: Four points are randomly chosen in the plane. What is the probability that the quadrilateral they form is convex?