Question

一个由 $11$ 名男性和 $12$ 名女性组成的俱乐部，需要从成员中选出一个委员会，使委员会中的女性人数比男性人数多 $1$ 。委员会最少可以有一名成员，最多可以有 $23$ 名成员。设 $N$ 为可组成的委员会数量。求所有整除 $N$ 的质数之和。

A club consisting of $11$ men and $12$ women needs to choose a committee from among its members so that the number of women on the committee is one more than the number of men on the committee. The committee could have as few as $1$ member or as many as $23$ members. Let $N$ be the number of such committees that can be formed. Find the sum of the prime numbers that divide $N.$

答案

答案：81

知识点：组合范德蒙德卷积勒让德公式质因数分解

难度评级：2450

解答：

有 $k$ 名男性的委员会有 $k + 1$ 名女性，所以 $\begin{aligned} N &= \sum_{k=0}^{11} \binom{11}{k}\binom{12}{k+1} \\ &= \sum_{k=0}^{11} \binom{11}{k}\binom{12}{11-k} \\ &= \binom{23}{11} \end{aligned}$ 由范德蒙德恒等式得到（两边都在数从全部 $23$ 人中选 $11$ 人的方法数）。

现在分解 $\binom{23}{11} = \frac{23!}{11!\,12!}$ 。质数 $13$ 、 $17$ 、 $19$ 、 $23$ 都出现在分子中而不出现在分母中。由勒让德公式， $2$ 的指数为 $19 - 8 - 10 = 1$ ， $3$ 的指数为 $9 - 4 - 5 = 0$ ， $5$ 的指数为 $4 - 2 - 2 = 0$ ， $7$ 的指数为 $3 - 1 - 1 = 1$ ， $11$ 的指数为 $2 - 1 - 1 = 0$ 。因此 $N = 2 \cdot 7 \cdot 13 \cdot 17 \cdot 19 \cdot 23$ 。

整除 $N$ 的质数之和为 $2 + 7 + 13 + 17 + 19 + 23 = 81$ 。

A committee with $k$ men has $k + 1$ women, so $\begin{aligned} N &= \sum_{k=0}^{11} \binom{11}{k}\binom{12}{k+1} \\ &= \sum_{k=0}^{11} \binom{11}{k}\binom{12}{11-k} \\ &= \binom{23}{11} \end{aligned}$ by Vandermonde's identity (both sides count ways to choose $11$ people from all $23$ ).

Now factor $\binom{23}{11} = \frac{23!}{11!\,12!}.$ The primes $13,$ $17,$ $19,$ $23$ each appear in the numerator but not the denominator. By Legendre's formula the exponent of $2$ is $19 - 8 - 10 = 1,$ of $3$ is $9 - 4 - 5 = 0,$ of $5$ is $4 - 2 - 2 = 0,$ of $7$ is $3 - 1 - 1 = 1,$ and of $11$ is $2 - 1 - 1 = 0.$ Hence $N = 2 \cdot 7 \cdot 13 \cdot 17 \cdot 19 \cdot 23.$

The sum of the primes dividing $N$ is $2 + 7 + 13 + 17 + 19 + 23 = 81.$

2020 AIME I 第 7 题

答案：81

难度评级：2450

解答：

其他年份的第 7 题