Question

En un grupo de nueve personas, cada persona estrecha la mano exactamente a otras dos personas del grupo. Sea $N$ el número de formas en que puede darse este patrón de apretones de manos. Se consideran dos disposiciones 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

Respuesta: 16

Conceptos:teoría de grafos arreglos circulares análisis por casos

Nivel de dificultad: 3060

Pista pequeña:

Que cada persona estreche exactamente dos manos divide a las nueve personas en ciclos de longitud al menos $3$ .

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

Pista grande:

Un ciclo con $k$ personas elegidas puede formarse de $\frac{(k-1)!}{2}$ maneras; sume sobre las particiones $3+3+3,$ $3+6,$ $4+5,$ y $9$ .

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$

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:$ hay $\frac{1}{3!}\binom{9}{3}\binom{6}{3} = 280$ maneras de dividir a las personas en tres tríos no ordenados, con un ciclo en cada trío: $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

Respuesta: 16

Nivel de dificultad: 3060

Pista pequeña:

Pista grande:

Solución:

El Problema 14 en otros años