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

Google