Question

十个成年人进入一个房间，脱下鞋子并把鞋子扔成一堆。之后，一个孩子随机地把每只左鞋与一只右鞋配成一双，不考虑它们是否原本属于同一个人。对于每个满足 $k \lt 5$ 的正整数 $k$ ，任意由孩子配出的 $k$ 双鞋都不会恰好只涉及同样数量的成年人。这个事件的概率为 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质正整数。求 $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.$

答案

答案：28

知识点：排列基本概率

难度评级：3060

解答：

孩子的配对可以看作把左鞋 $j$ 配给右鞋 $\pi(j)$ ，其中 $\pi$ 是 $\{1, \ldots, 10\}$ 上的均匀随机排列。由 $k$ 双鞋组成的集合含有 $k$ 只左鞋和 $k$ 只右鞋，所以它恰好涉及 $k$ 个成年人，当且仅当这些成年人的编号在 $\pi$ 下封闭；也就是说，该集合是 $\pi$ 的若干个循环的并。因此条件等价于 $\pi$ 没有长度小于 $5$ 的循环。

循环长度必须把 $10$ 分拆成每部分至少为 $5$ ：要么是一个 $10$ -循环，要么是两个 $5$ -循环。共有 $9!$ 个十循环，而两个 $5$ -循环的排列数为 $\frac{1}{2}\binom{10}{5}(4!)^2 = \frac{9!}{5}$ 。

概率为 $\frac{9! + \frac{1}{5} \cdot 9!}{10!} = \frac{1 + \frac{1}{5}}{10} = \frac{3}{25},$ 所以 $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 第 13 题

答案：28

难度评级：3060

解答：

其他年份的第 13 题