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