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.

Source
Suggested Reading

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}\)

Subscribe to Cheenta at Youtube