Question

Diez adultos entran en una habitación, se quitan los zapatos y arrojan sus zapatos a un montón. Después, un niño empareja al azar cada zapato izquierdo con un zapato derecho sin tener en cuenta qué zapatos van juntos. La probabilidad de que, para todo entero positivo $k \lt 5,$ ninguna colección de $k$ pares formados por el niño contenga los zapatos de exactamente $k$ de los adultos es $\frac{m}{n},$ donde $m$ y $n$ son enteros positivos primos entre sí. Halla $m + n.$

Ten adults enter a room, remove their shoes, and toss their shoes into a pile. Later, a child randomly pairs each left shoe with a right shoe without regard to which shoes belong together. The probability that for every positive integer $k \lt 5,$ no collection of $k$ pairs made by the child contains the shoes from exactly $k$ of the adults is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

Respuesta

Solución:

El emparejamiento del niño hace corresponder el zapato izquierdo $j$ con el zapato derecho $\pi(j)$ para una permutación uniformemente aleatoria $\pi$ de $\{1, \ldots, 10\}.$ Una colección de $k$ pares usa $k$ zapatos izquierdos y $k$ derechos, así que involucra exactamente $k$ adultos precisamente cuando los índices de esos adultos son cerrados bajo $\pi$ , es decir, cuando la colección es una unión de ciclos de $\pi.$ Por tanto la condición dice que $\pi$ no tiene ningún ciclo de longitud menor que $5.$

Las longitudes de los ciclos deben partir $10$ en partes de tamaño al menos $5:$ o bien un $10$ -ciclo o bien dos $5$ -ciclos. Hay $9!$ ciclos de diez, y $\frac{1}{2}\binom{10}{5}(4!)^2 = \frac{9!}{5}$ permutaciones que son productos de dos $5$ -ciclos.

La probabilidad es $\frac{9! + \frac{1}{5} \cdot 9!}{10!} = \frac{1 + \frac{1}{5}}{10} = \frac{3}{25},$ así que $m + n = 3 + 25 = 28.$

The child's pairing matches left shoe $j$ with right shoe $\pi(j)$ for a uniformly random permutation $\pi$ of $\{1, \ldots, 10\}.$ A collection of $k$ pairs uses $k$ left and $k$ right shoes, so it involves exactly $k$ adults precisely when those adults' indices are closed under $\pi$ — that is, when the collection is a union of cycles of $\pi.$ The condition therefore says $\pi$ has no cycle of length less than $5.$

The cycle lengths must partition $10$ into parts of size at least $5:$ either one $10$ -cycle or two $5$ -cycles. There are $9!$ ten-cycles, and $\frac{1}{2}\binom{10}{5}(4!)^2 = \frac{9!}{5}$ permutations that are products of two $5$ -cycles.

The probability is $\frac{9! + \frac{1}{5} \cdot 9!}{10!} = \frac{1 + \frac{1}{5}}{10} = \frac{3}{25},$ so $m + n = 3 + 25 = 28.$

2014 AIME II Problema 13

Solución:

El Problema 13 en otros años