2014 AIME II 第 13 题

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)

配对定义了一个随机排列；由

k

双鞋组成并恰好涉及

k

个成年人的集合就是若干个循环的并

Pairing left shoe

j

with right shoe

\pi(j)

defines a random permutation; a collection of

k

pairs using exactly

k

adults’ shoes is a union of cycles

大提示：

条件等价于

\pi

的每个循环长度都至少为

5

：数一个

10

-循环和两个

5

-循环的乘积

The condition says every cycle of

\pi

has length at least

5:

count

10

-cycles and products of two

5

-cycles

解答：

孩子的配对可以看作把左鞋

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}\text{，}

所以

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 题