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<a_2<a_3<...<a_{1000}$ 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<a_1+1<a_2+1,a_3+1<...<a_{1000}+1$ ( $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}$ .

Solution 4 (short)

In the "average case", the numbers evenly partition the interval [0,2016] into 1001 parts. Then because it asks for the expected value of the least element the answer is $\frac{2016}{1001}$ .

-tigershark22

Video Solution

https://www.youtube.com/watch?v=t-yHTkGkMK4 ~anellipticcurveoverq

Generalization

https://artofproblemsolving.com/wiki/index.php/1981_IMO_Problems/Problem_2

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

Page

Toolbox

Search