2012 AIME II Problem 14

Question

In a group of nine people each person shakes hands with exactly two of the other people from the group. Let

N

be the number of ways this handshaking can occur. Consider two handshaking arrangements different if and only if at least two people who shake hands under one arrangement do not shake hands under the other arrangement. Find the remainder when

N

is divided by

1000.

Answer

Answer: 16

Concepts:graph theory circular arrangements casework

Difficulty rating: 3060

Small hint:

Everyone shaking exactly two hands splits the nine people into cycles of length at least

3

Big hint:

A cycle on

k

chosen people can be formed in

\frac{(k-1)!}{2}

ways; sum over the partitions

3+3+3,

3+6,

4+5,

and

9

Solution:

An arrangement in which everyone shakes exactly two hands is a disjoint union of cycles of length at least

3

covering all nine people. The possible cycle-length partitions of

9

are

3+3+3,

3+6,

4+5,

and

9.

On

k

given people, the number of distinct cycles is

\frac{(k-1)!}{2}.

For

3+3+3:

split into three unordered triples in

\frac{1}{3!}\binom{9}{3}\binom{6}{3} = 280

ways, one cycle each:

280.

For

3+6:

\binom{9}{3} \cdot 1 \cdot \frac{5!}{2} = 84 \cdot 60 = 5040.

For

4+5:

\binom{9}{4} \cdot \frac{3!}{2} \cdot \frac{4!}{2}

= 126 \cdot 3 \cdot 12 = 4536.

For a single

9

-cycle:

\frac{8!}{2} = 20160.

In total

N = 280 + 5040

+ 4536 + 20160 = 30016,

so the remainder modulo

1000

is

16.