Try this beautiful problem from the American Invitational Mathematics Examination, AIME, 2015 based on Arithmetic Mean.
Arithmetic Mean of Number Theory – AIME 2015
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\).
- is 107
- is 431
- is 840
- cannot be determined from the given information
Key Concepts
Inequalities
Algebra
Number Theory
Check the Answer
But try the problem first…
Answer: is 431.
AIME, 2015, Question 12
Elementary Number Theory by David Burton
Try with Hints
First hint
Each 1000-element subset \({ a_1, a_2,a_3,…,a_{1000}}\) of \({1,2,3,…,2015}\) with \(a_1<a_2<a_3<…<a_{1000}\) contributes \(a_1\) to sum of least element of each subset and set \({a_1+1,a_2+1,a_3+1,…,a_{1000}+1}\). \(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
Second Hint
Thus, the number of ways to choose the set \({k,a_1+1,a_2+1,a_3+1,…,a_{1000}+1}\) is equal to the sum. But choosing a set \({k,a_1+1,a_2+1,a_3+1,…,a_{1000}+1}\) is same as choosing a 1001-element subset from \({1,2,3,…,2016}\)!
Final Step
average =\(\frac{2016}{1001}\)=\(\frac{288}{143}\). Then \(p+q=288+143={431}\)
Other useful links
- https://www.cheenta.com/cubes-and-rectangles-math-olympiad-hanoi-2018/
- https://www.youtube.com/watch?v=ST58GTF95t4&t=140s
Related Program
Math Olympiad Program… taught by Olympians and researchers