Question

En un grupo de nueve personas, cada persona estrecha la mano exactamente a dos de las otras personas del grupo. Sea $N$ el número de formas en que puede ocurrir este apretón de manos. Se consideran dos disposiciones de apretones diferentes si y solo si al menos dos personas que se dan la mano en una disposición no se dan la mano en la otra. Halle el residuo cuando $N$ se divide entre $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.$

Respuesta

Solución:

Una disposición en la que todos dan exactamente dos apretones es una unión disjunta de ciclos de longitud al menos $3$ que cubre a las nueve personas. Las particiones posibles de las longitudes de ciclo de $9$ son $3+3+3,$ $3+6,$ $4+5,$ y $9.$ Sobre $k$ personas dadas, el número de ciclos distintos es $\frac{(k-1)!}{2}.$

Para $3+3+3:$ dividir en tres tríos no ordenados de $\frac{1}{3!}\binom{9}{3}\binom{6}{3} = 280$ maneras, un ciclo cada uno: $280.$ Para $3+6:$ $\binom{9}{3} \cdot 1 \cdot \frac{5!}{2} = 84 \cdot 60 = 5040.$ Para $4+5:$ $\binom{9}{4} \cdot \frac{3!}{2} \cdot \frac{4!}{2}$ $= 126 \cdot 3 \cdot 12 = 4536.$ Para un único $9$ -ciclo: $\frac{8!}{2} = 20160.$

En total $N = 280 + 5040$ $+ 4536 + 20160 = 30016,$ así que el residuo módulo $1000$ es $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 Problema 14

Solución:

El Problema 14 en otros años