Difference between revisions of "2015 AIME I Problems/Problem 12"
| Line 2: | Line 2: | ||
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 <math> \frac{p}{q} </math>, where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p + q</math>. | 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 <math> \frac{p}{q} </math>, where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p + q</math>. | ||
| + | |||
| + | ==Hint== | ||
| + | Use the Hockey Stick Identity in the form | ||
| + | |||
| + | <cmath>\binom{a}{a} + \binom{a+1}{a} + \binom{a+2}{a} + \dots + \binom{b}{a} = \binom{b+1}{a+1}.</cmath> | ||
| + | |||
| + | (This is best proven by a combinatorial argument that coincidentally pertains to the problem: count two ways the number of subsets of the first <math>(b + 1)</math> numbers with <math>(a + 1)</math> elements whose least element is <math>i</math>, for <math>1 \le i \le b - a</math>.) | ||
| + | |||
| + | ==Solution== | ||
| + | Let <math>M</math> be the desired mean. Then because <math>\dbinom{2015}{1000}</math> subsets have 1000 elements and <math>\dbinom{2015 - i}{999}</math> have <math>i</math> 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 <math>n! = n \cdot (n-1)!</math>, we deduce that | ||
| + | <cmath>M = \frac{2016}{1001} = \frac{288}{143}.</cmath> | ||
| + | The answer is <math>\boxed{431}.</math> | ||
== See also == | == See also == | ||
Revision as of 18:43, 20 March 2015
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. 
