Question

考虑集合 $\{1, 2, 3, \ldots, 2015\}$ 的所有 $1000$ 元子集。从每个这样的子集中选出最小元素。所有这些最小元素的算术平均数为 $\frac{p}{q}$ ，其中 $p$ 与 $q$ 是互质的正整数。求 $p + q$ 。

Consider all $1000$ -element subsets of the set $\{1, 2, 3, \ldots, 2015\}.$ From each such subset choose the least element. The arithmetic mean of all of these least elements is $\frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. Find $p + q.$

答案

答案：431

知识点：组合期望值双射

难度评级：3270

解答：

一个 $1000$ 元子集的最小元素为 $j$ ，当且仅当它包含 $j$ 并从更大的元素中选 $999$ 个，所以这样的子集有 $\binom{2015-j}{999}$ 个，其最小元素为 $j$ 。平均数为 $\frac{\sum_{j} j\binom{2015-j}{999}}{\binom{2015}{1000}}$ 。

分子可以看作一个具体计数：为了构造 $\{0, 1, \ldots, 2015\}$ 的一个 $1001$ 元子集，使其第二小元素为 $j$ ，从 $\{0, \ldots, j-1\}$ 中选最小元素（有 $j$ 种），再从 $\{j+1, \ldots, 2015\}$ 中选上方的 $999$ 个元素。对 $j$ 求和会把每个 $1001$ 元子集恰好数一次，所以 $\sum_j j\binom{2015-j}{999} = \binom{2016}{1001}$ 。

因此平均数为 $\frac{\binom{2016}{1001}}{\binom{2015}{1000}} = \frac{2016}{1001} = \frac{288}{143}$ ，已经是最简分数，所以 $p + q = 288 + 143 = 431$ 。

A $1000$ -element subset has least element $j$ exactly when it contains $j$ together with $999$ larger elements, so $\binom{2015-j}{999}$ of the subsets have least element $j.$ The mean is therefore $\frac{\sum_{j} j\binom{2015-j}{999}}{\binom{2015}{1000}}.$

The numerator counts something concrete: to build a $1001$ -element subset of $\{0, 1, \ldots, 2015\}$ whose second-smallest element is $j,$ choose its smallest element from $\{0, \ldots, j-1\}$ ( $j$ ways) and its top $999$ elements from $\{j+1, \ldots, 2015\}.$ Summing over $j$ produces every $1001$ -element subset exactly once, so $\sum_j j\binom{2015-j}{999} = \binom{2016}{1001}.$

Hence the mean is $\frac{\binom{2016}{1001}}{\binom{2015}{1000}} = \frac{2016}{1001} = \frac{288}{143},$ which is in lowest terms, and $p + q = 288 + 143 = 431.$

2015 AIME I 第 12 题

答案：431

难度评级：3270

解答：

其他年份的第 12 题