Difference between revisions of "2015 AIME I Problems/Problem 12"
Phoenixfire (talk | contribs) |
|||
Line 54: | Line 54: | ||
https://www.youtube.com/watch?v=t-yHTkGkMK4 | https://www.youtube.com/watch?v=t-yHTkGkMK4 | ||
~anellipticcurveoverq | ~anellipticcurveoverq | ||
+ | |||
+ | == Generalization == | ||
+ | https://artofproblemsolving.com/wiki/index.php/1981_IMO_Problems/Problem_2 | ||
== See also == | == See also == |
Revision as of 07:36, 20 February 2021
Contents
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
.
Solution 3(NOT RIGOROUS)
Let be the size of the large set and
be the size of the subset (i.e. in this problem,
and
). We can easily find the answers for smaller values of
and
:
For and
, the answer is
.
For and
, the answer is
.
For and
, the answer is
.
For and
, the answer is
.
For and
, the answer is
.
For and
, the answer is
.
At this point, we can see a pattern: our desired answer is always . Plugging in
and
, the answer is
, so
.
Video Solution
https://www.youtube.com/watch?v=t-yHTkGkMK4 ~anellipticcurveoverq
Generalization
https://artofproblemsolving.com/wiki/index.php/1981_IMO_Problems/Problem_2
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.