Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2015 AIME I Problems/Problem 12"
(→‎Solution)
Line 49: Line 49:
  
 
At this point, we can see a pattern: our desired answer is always <math>\frac{p+1}{q+1}</math>. Plugging in <math>p = 2015</math> and <math>q = 1000</math>, the answer is <math>\frac{2016}{1001}=\frac{288}{143}</math>, so <math>288 + 143 = \boxed{431}</math>.
 
At this point, we can see a pattern: our desired answer is always <math>\frac{p+1}{q+1}</math>. Plugging in <math>p = 2015</math> and <math>q = 1000</math>, the answer is <math>\frac{2016}{1001}=\frac{288}{143}</math>, so <math>288 + 143 = \boxed{431}</math>.
 +
 +
===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 <math>\frac{2016}{1001}</math>.
 +
 +
-tigershark22
  
 
==Video Solution==
 
==Video Solution==

Revision as of 20:51, 1 March 2021

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

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2015_AIME_I_Problems/Problem_12&oldid=148142"