Problem:
onsider 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 qp, where p and q are relatively prime positive integers. Find p+q.
Solution:
Consider the number of 1000-element subsets of {1,2,3,…,2015} with least element j,1≤j≤1016. Every such subset has 999 elements greater than j, and thus the number of such subsets is (9992015−j). Therefore the sum of all least elements of the subsets under consideration is ∑j=11016j(9992015−j). Thus the arithmetic mean in question is equal to (10002015)∑j=11016j(9992015−j).
Note that the number of 1001-element subsets of {0,1,2,…,2015} where j is the second smallest element is j(9992015−j) because there are j choices for the least element of the subset and (9992015−j) choices for the largest 999 elements. Thus ∑j=11016j(9992015−j)=(10012016).
Hence the required arithmetic mean is (10002015)∑j=11016j(9992015−j)=(10002015)(10012016)=10012016=143288.
The requested sum is 288+143=431.
OR
Another way to simplify ∑j=11016j(9992015−j) is to apply the Hockey Stick Theorem, ∑j=0k(jn+j)=(kn+k+1), to get ∑j=11016j(9992015−j)=∑j=01015(1016−j)(j999+j)=∑k=01015∑j=0k(j999+j)=∑k=01015(k1000+k)=(10152016)=(10012016).
The problems on this page are the property of the MAA's American Mathematics Competitions