2009 AIME II Problems/Problem 12
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.