Difference between revisions of "2009 AIME II Problems/Problem 12"
(New page: == Problem == From the set of integers <math>\{1,2,3,\dots,2009\}</math>, choose <math>k</math> pairs <math>\{a_i,b_i\}</math> with <math>a_i<b_i</math> so that no two pairs have a common ...) |
m |
||
(2 intermediate revisions by 2 users not shown) | |||
Line 4: | Line 4: | ||
== Solution == | == Solution == | ||
− | Suppose that we have a valid solution with <math>k</math> pairs. As all <math>a_i</math> and <math>b_i</math> are distinct, their sum is at least <math>1+2+3+\cdots+2k=k(2k+1)</math>. On the other hand, as the sum of each pair is distinct and at most equal to <math>2009</math>, the sum of all <math>a_i</math> and <math>b_i</math> is at most <math>2009 + (2009-1) + \cdots + (2009-(k-1)) = k(4019-k) | + | Suppose that we have a valid solution with <math>k</math> pairs. As all <math>a_i</math> and <math>b_i</math> are distinct, their sum is at least <math>1+2+3+\cdots+2k=k(2k+1)</math>. On the other hand, as the sum of each pair is distinct and at most equal to <math>2009</math>, the sum of all <math>a_i</math> and <math>b_i</math> is at most <math>2009 + (2009-1) + \cdots + (2009-(k-1)) = \frac{k(4019-k)}{2}</math>. |
− | Hence we get a necessary condition on <math>k</math>: For a solution to exist, we must have <math>k(4019-k) | + | Hence we get a necessary condition on <math>k</math>: For a solution to exist, we must have <math>\frac{k(4019-k)}{2} \geq k(2k+1)</math>. As <math>k</math> is positive, this simplifies to <math>\frac{4019-k}{2} \geq 2k+1</math>, whence <math>5k\leq 4017</math>, and as <math>k</math> is an integer, we have <math>k\leq \lfloor 4017/5\rfloor = 803</math>. |
If we now find a solution with <math>k=803</math>, we can be sure that it is optimal. | If we now find a solution with <math>k=803</math>, we can be sure that it is optimal. | ||
Line 26: | Line 26: | ||
Thus we have shown that there is a solution for <math>k=\boxed{803}</math> and that for larger <math>k</math> no solution exists. | Thus we have shown that there is a solution for <math>k=\boxed{803}</math> and that for larger <math>k</math> no solution exists. | ||
+ | |||
+ | |||
+ | == Video Solution == | ||
+ | |||
+ | https://youtu.be/yVP2MhOMSy4?si=ZC4Zo4xKe867uM8X | ||
+ | |||
+ | ~MathProblemSolvingSkills.com | ||
+ | |||
+ | |||
== See Also == | == See Also == | ||
{{AIME box|year=2009|n=II|num-b=11|num-a=13}} | {{AIME box|year=2009|n=II|num-b=11|num-a=13}} | ||
+ | {{MAA Notice}} |
Latest revision as of 14:20, 14 May 2024
Contents
Problem
From the set of integers , choose
pairs
with
so that no two pairs have a common element. Suppose that all the sums
are distinct and less than or equal to
. Find the maximum possible value of
.
Solution
Suppose that we have a valid solution with pairs. As all
and
are distinct, their sum is at least
. On the other hand, as the sum of each pair is distinct and at most equal to
, the sum of all
and
is at most
.
Hence we get a necessary condition on : For a solution to exist, we must have
. As
is positive, this simplifies to
, whence
, and as
is an integer, we have
.
If we now find a solution with , we can be sure that it is optimal.
From the proof it is clear that we don't have much "maneuvering space", if we want to construct a solution with .
We can try to use the
smallest numbers:
to
.
When using these numbers, the average sum will be
. Hence we can try looking for a nice systematic solution that achieves all sums between
and
, inclusive.
Such a solution indeed does exist, here is one:
Partition the numbers to
into four sequences:
Sequences and
have
elements each, and the sums of their corresponding elements are
.
Sequences
and
have
elements each, and the sums of their corresponding elements are
.
Thus we have shown that there is a solution for and that for larger
no solution exists.
Video Solution
https://youtu.be/yVP2MhOMSy4?si=ZC4Zo4xKe867uM8X
~MathProblemSolvingSkills.com
See Also
2009 AIME II (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.