Question

九个人组成一组，每个人都恰好与组内另外两个人握手。令 $N$ 为这种握手方式的数量。若且唯若至少有两个人在一种安排中握手、而在另一种安排中不握手，就认为这两种握手安排不同。求 $N$ 除以 $1000$ 的余数。

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

答案

答案：16

知识点：图论环形排列分类讨论

难度评级：3060

解答：

每个人都恰好与两人握手的安排，就是覆盖所有九个人的若干个互不相交、长度至少为 $3$ 的环。 $9$ 的可能环长分拆为 $3+3+3$ 、 $3+6$ 、 $4+5$ 和 $9$ 。在给定的 $k$ 个人上，不同环的数量为 $\frac{(k-1)!}{2}$ 。

对于 $3+3+3$ ：将九个人分成三个无序三人组有 $\frac{1}{3!}\binom{9}{3}\binom{6}{3} = 280$ 种，每组三人只有一个环，共 $280$ 种。对于 $3+6$ ：有 $\binom{9}{3} \cdot 1 \cdot \frac{5!}{2} = 84 \cdot 60 = 5040$ 种。对于 $4+5$ ：有 $\binom{9}{4} \cdot \frac{3!}{2} \cdot \frac{4!}{2}$ $= 126 \cdot 3 \cdot 12 = 4536$ 种。对于一个 $9$ -环：有 $\frac{8!}{2} = 20160$ 种。

总计 $N = 280 + 5040$ $+ 4536 + 20160 = 30016$ ，所以模 $1000$ 的余数为 $16$ 。

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 第 14 题

答案：16

难度评级：3060

解答：

其他年份的第 14 题