2015 AIME I Problems/Problem 12
Problem
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 , where
and
are relatively prime positive integers. Find
.
Hint
Use the Hockey Stick Identity in the form
(This is best proven by a combinatorial argument that coincidentally pertains to the problem: count two ways the number of subsets of the first numbers with
elements whose least element is
, for
.)
Solution
Solution 1
Let be the desired mean. Then because
subsets have 1000 elements and
have
as their least element,
Using the definition of binomial coefficient and the identity
, we deduce that
The answer is
Solution 2
Each 1000-element subset of
with
contributes
to the sum of the least element of each subset. Now, consider the set
. There are
ways to choose a positive integer
such that
(
can be anything from
to
inclusive). Thus, the number of ways to choose the set
is equal to the sum. But choosing a set
is the same as choosing a 1001-element subset from
!
Thus, the average is . Our answer is
.
See also
2015 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 11 |
Followed by Problem 13 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.