Difference between revisions of "2015 AIME I Problems/Problem 12"
Kingsave3166 (talk | contribs) |
|||
Line 36: | Line 36: | ||
{{AIME box|year=2015|n=I|num-b=11|num-a=13}} | {{AIME box|year=2015|n=I|num-b=11|num-a=13}} | ||
{{MAA Notice}} | {{MAA Notice}} | ||
− | [[Category:Introductory | + | [[Category:Introductory Combinatorics Problems]] |
Revision as of 17:45, 18 May 2015
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.