Subset Mean

From AIME I 2015:

Consider all -element subsets of the set . From each subset choose the least element. Find the arithmetic mean of these least elements.

Solution

There are subsets of cardinality . How many of these subsets have as the least element? To construct each of these subsets, we choose to be in the set, and then of the remaining numbers. So there are subsets with as the least element.

What about the number of subsets that have as the least element? Like before, we choose to be in each subset. Since must be the least element, the remaining elements must be from the elements greater than . Then there are 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 . 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 and consecutive , 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.