# Subset Mean

From AIME I 2015:

Consider all $1000$-element subsets of the set $\{1,2, \ldots ,2015 \}$. From each subset choose the least element. Find the arithmetic mean of these least elements.

## Solution

There are $\binom{2015}{1000}$ subsets of cardinality $1000$. How many of these subsets have $1$ as the least element? To construct each of these subsets, we choose $1$ to be in the set, and then $999$ of the remaining $2014$ numbers. So there are $\binom{2014}{999}$ subsets with $1$ as the least element.

What about the number of subsets that have $i$ as the least element? Like before, we choose $i$ to be in each subset. Since $i$ must be the least element, the remaining elements must be from the $2015 - i$ elements greater than $i$. Then there are $\binom{2015-i}{999}$ such subsets.

To find the arithmetic mean of the least elements, we sum the least elements and divide by the number of subsets of size $1000$. The sum of the least elements is

How can we simplify this? Here we recognize that the expression contains a sum of binomial coefficients with $k=999$ and consecutive $n$, which suggests that the Hockey Stick Identity would be useful. Letâ€™s split up these terms so we can apply it.

Now that we have the sum, we solve for the arithmetic mean.