Arithmetic Mean | AIME I, 2015 | Question 12

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

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

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

average =\(\frac{2016}{1001}\)=\(\frac{288}{143}\). Then \(p+q=288+143={431}\)

Subscribe to Cheenta at Youtube