AMC 10 · 2005 · #25

Grade 7 probability

Archetype Casework by Position / Vertex Type └ Sub-archetype Count of Type

probability-basicpermutations-basicderangementfundamental-counting-principle caseworksystematic-enumerationspatial-visualization ↑ Prerequisites: probability-basicpermutations-basicfundamental-counting-principle

📏 Long solution 💡 4 insights

Problem

Six ants stand on the six corners of a regular octahedron and each walks along one edge at random. Find the probability that no two ants land on the same corner.

Pick an answer.

(A)

$\frac {5}{256}$

(B)

$\frac {21}{1024}$

(C)

$\frac {11}{512}$

(D)

$\frac {23}{1024}$

(E)

$\frac {3}{128}$

How to solve

Strategy Organize Information in More Ways

The only feature of the octahedron that matters here is that each vertex is joined to all the others except its opposite. So bundle the six vertices into three opposite pairs; the rule 'an ant may not stay and may not go to its opposite' becomes the single rule 'no ant may land inside its own pair'. Then record only how many ants travel from each pair to each other pair. That is a 3 × 3 table whose rows and columns all add to 2 and whose diagonal is 0, and only three such tables exist -- a list short enough to finish by hand, with no risk of missing or double-counting a case.

1STEP 1

Turn probability into counting

The probability becomes a count over 4096 equally likely outcomes.

4⁶ = 4096 equally likely outcomes

2STEP 2

Adjacency: everything but the opposite

The only non-edges are the three opposite pairs.

C(6, 2) - 12 = 15 - 12 = 3 non-edges = the 3 pairs of opposite vertices

3STEP 3

No collisions means a perfect shuffle

No collisions means the move is a full rearrangement.

σ is a permutation of the 6 vertices with σ(v) ≠ v and σ(v) ≠ v

4STEP 4

Bundle the opposites into three pairs

Bundling the opposites reduces everything to one rule: no ant stays in its pair.

P₁ = {1, 1'}, P₂ = {2, 2'}, P₃ = {3, 3'}; σ(v) ∉ P_i when v ∈ P_i

5STEP 5

Build a 3-by-3 traffic table

A three-by-three traffic table records the moves between pairs.

Σ_j M_ij = 2, Σ_i M_ij = 2, M_ii = 0

6STEP 6

Only three tables are possible

One number decides the whole table, so only three tables exist.

M = 0 & x & 2-x ; 2-x & 0 & x ; x & 2-x & 0 , x ∈ {0, 1, 2}

7STEP 7

Case x = 0 and case x = 2: pairs move whole

The two rotating cases give 16 outcomes.

2 · 2 · 2 = 8 each, 8 + 8 = 16

8STEP 8

Case x = 1: every pair splits up

The splitting case gives 64 more.

2³ · 2³ = 8 · 8 = 64

9STEP 9

Add the cases and divide

Adding and reducing gives 5/256, choice (A).

(16 + 64)/4096 = 80/4096 = 5/256

Answer

5/256

Count the same 80 a second time by sorting the shuffles by cycle shape instead of by traffic table. No ant stays put, so no cycle of length 1 is allowed, leaving shapes 2+2+2, 3+3, 4+2, and 6. Three 2-cycles means splitting the six vertices into three edges: of the 15 ways to split six points into three pairs, inclusion-exclusion on the three forbidden opposite pairs leaves 15 - 3 · 3 + 3 - 1 = 8. Two 3-cycles: a triangle must take one vertex from each opposite pair, so there are 2³/2 = 4 splits, and each triangle can be cycled 2 ways, giving 4 · 2 · 2 = 16. A 4-cycle plus a 2-cycle: 12 choices of edge for the 2-cycle, and the four remaining vertices admit exactly one 4-cycle, usable in 2 directions, giving 24. A single 6-cycle: of the 60 six-point cycles, inclusion-exclusion on the three forbidden opposite pairs leaves 60 - 3 · 24 + 3 · 12 - 8 = 16 undirected cycles, so 32 directed ones. Total 8 + 16 + 24 + 32 = 80 -- the same answer from a completely different breakdown. This check matters because the five choices correspond to counts of 80, 84, 88, 92, 96 out of 4096; they are all near 2%, so nothing here can be settled by estimating.

💡Key takeaway

On an octahedron every vertex is joined to all but its opposite, so pair up the opposites and six ants scrambling in space become a nine-box table you can finish by hand.

Turn probability into counting
Adjacency: everything but the opposite
No collisions means a perfect shuffle
Bundle the opposites into three pairs
Build a 3-by-3 traffic table
Only three tables are possible
Case x = 0 and case x = 2: pairs move whole
Case x = 1: every pair splits up
Add the cases and divide