2015 AIME I Problems/Problem 12
Contents
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 
, where 
and 
are relatively prime positive integers. Find 
.
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}.\]](http://latex.artofproblemsolving.com/5/9/9/5995d78139aa36d79bf26ac228389406a12a6261.png)
(This is best proven by a combinatorial argument that coincidentally pertains to the problem: count two ways the number of subsets of the first 
numbers with 
elements whose least element is 
, for 
.)
Solution
Let 
be the desired mean. Then because 
subsets have 1000 elements and 
have 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 
, we deduce that
![\[M = \frac{2016}{1001} = \frac{288}{143}.\]](http://latex.artofproblemsolving.com/e/1/b/e1b3d7637ffbc13c55b4c821e91100ba4943e58e.png)
The answer is 
See also
| 2015 AIME I (Problems • Answer Key • Resources) | ||
| Preceded by Problem 11 |
Followed by Problem 13 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
