# 2015 AIME I Problems/Problem 12

## Problem

Consider all 1000-element subsets of the set {1, 2, 3, ... , 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$.

## Hint

Use the Hockey Stick Identity in the form

$$\binom{a}{a} + \binom{a+1}{a} + \binom{a+2}{a} + \dots + \binom{b}{a} = \binom{b+1}{a+1}.$$

(This is best proven by a combinatorial argument that coincidentally pertains to the problem: count two ways the number of subsets of the first $(b + 1)$ numbers with $(a + 1)$ elements whose least element is $i$, for $1 \le i \le b - a$.)

## Solution

### Solution 1

Let $M$ be the desired mean. Then because $\dbinom{2015}{1000}$ subsets have 1000 elements and $\dbinom{2015 - i}{999}$ have $i$ as their least element, \begin{align*} \binom{2015}{1000} M &= 1 \cdot \binom{2014}{999} + 2 \cdot \binom{2013}{999} + \dots + 1016 \cdot \binom{999}{999} \\ &= \binom{2014}{999} + \binom{2013}{999} + \dots + \binom{999}{999} \\ & + \binom{2013}{999} + \binom{2012}{999} + \dots + \binom{999}{999} \\ & \dots \\ & + \binom{999}{999} \\ &= \binom{2015}{1000} + \binom{2014}{1000} + \dots + \binom{1000}{1000} \\ &= \binom{2016}{1001}. \end{align*} Using the definition of binomial coefficient and the identity $n! = n \cdot (n-1)!$, we deduce that $$M = \frac{2016}{1001} = \frac{288}{143}.$$ The answer is $\boxed{431}.$

### Solution 2

Each 1000-element subset $\left\{ a_1, a_2,a_3,...,a_{1000}\right\}$ of $\left\{1,2,3,...,2015\right\}$ with $a_1 contributes $a_1$ to the sum of the least element of each subset. Now, consider the set $\left\{a_1+1,a_2+1,a_3+1,...,a_{1000}+1\right\}$. There are $a_1$ ways to choose a positive integer $k$ such that $k ($k$ can be anything from $1$ to $a_1$ inclusive). Thus, the number of ways to choose the set $\left\{k,a_1+1,a_2+1,a_3+1,...,a_{1000}+1\right\}$ is equal to the sum. But choosing a set $\left\{k,a_1+1,a_2+1,a_3+1,...,a_{1000}+1\right\}$ is the same as choosing a 1001-element subset from $\left\{1,2,3,...,2016\right\}$!

Thus, the average is $\frac{\binom{2016}{1001}}{\binom{2015}{1000}}=\frac{2016}{1001}=\frac{288}{143}$. Our answer is $p+q=288+143=\boxed{431}$.

### Solution 3(NOT RIGOROUS)

Let $p$ be the size of the large set and $q$ be the size of the subset (i.e. in this problem, $p = 2015$ and $q = 1000$). We can easily find the answers for smaller values of $p$ and $q$:

For $p = 2$ and $q = 2$, the answer is $1$.

For $p = 3$ and $q = 2$, the answer is $\frac43$.

For $p = 4$ and $q = 2$, the answer is $\frac53$.

For $p = 3$ and $q = 3$, the answer is $1$.

For $p = 4$ and $q = 3$, the answer is $\frac54$.

For $p = 5$ and $q = 3$, the answer is $\frac32$.

At this point, we can see a pattern: our desired answer is always $\frac{p+1}{q+1}$. Plugging in $p = 2015$ and $q = 1000$, the answer is $\frac{2016}{1001}=\frac{288}{143}$, so $288 + 143 = \boxed{431}$.