2015 AIME I Problems/Problem 12

Revision as of 18:46, 20 March 2015 by Suli (talk | contribs) (Solution)

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

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}.$

See also

2015 AIME I (ProblemsAnswer KeyResources)
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. AMC logo.png