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=11016​j(9992015−j​). Thus the arithmetic mean in question is equal to (10002015​)∑j=11016​j(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=11016​j(9992015−j​)=(10012016​).
Hence the required arithmetic mean is (10002015​)∑j=11016​j(9992015−j​)​=(10002015​)(10012016​)​=10012016​=143288​.
The requested sum is 288+143=431​.
OR
Another way to simplify ∑j=11016​j(9992015−j​) is to apply the Hockey Stick Theorem, ∑j=0k​(jn+j​)=(kn+k+1​), to get ∑j=11016​j(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