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

答案

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

2012 AIME II Problem 14

Solution:

Problem 14 in Other Years