2009 AIME II Problems/Problem 12
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 .
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.
|2009 AIME II (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|