2009 AIME II Problems/Problem 12
From AoPSWiki
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.
See Also
| 2009 AIME II (Problems • Resources) | ||
| Preceded by Problem 11 | Followed by Problem 13 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
