Question

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.$

Answer

Solution:

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 Problem 12

Solution:

Problem 12 in Other Years