AIME II 2009 #12

[stupidityismygam]

From the set of integers [unparseable or potentially dangerous latex formula] choose [unparseable or potentially dangerous latex formula] pairs [unparseable or potentially dangerous latex formula] with [unparseable or potentially dangerous latex formula] so that no two pairs have a common element. Suppose that all the sums [unparseable or potentially dangerous latex formula] are distinct and less than or equal to [unparseable or potentially dangerous latex formula] Find the maximum possible value of [unparseable or potentially dangerous latex formula]

[88bobcat]

[stupidityismygam]

Not quite. It is higher than that.

I'll post a solution soon.

[sinkokuyou]

solution:
Suppose that we have a valid solution with k pairs. As all [unparseable or potentially dangerous latex formula] and [unparseable or potentially dangerous latex formula] are distinct, their sum is at least [unparseable or potentially dangerous latex formula]. On the other hand, as the sum of each pair is distinct and at most equal to 2009, the sum of all [unparseable or potentially dangerous latex formula] and [unparseable or potentially dangerous latex formula] is at most [unparseable or potentially dangerous latex formula].
Hence we get a necessary condition on k: For a solution to exist, we must have [unparseable or potentially dangerous latex formula]. As k is positive, this simplifies to [unparseable or potentially dangerous latex formula], whence [unparseable or potentially dangerous latex formula], and as k is an integer, we have [unparseable or potentially dangerous latex formula].
If we now find a solution with k=803, 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 k=803. We can try to use the 2k smallest numbers: 1 to [unparseable or potentially dangerous latex formula] 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 [unparseable or potentially dangerous latex formula] and [unparseable or potentially dangerous latex formula], inclusive.

Such a solution indeed does exist, here is one:

Partition the numbers 1 to 1606 into four sequences:
[unparseable or potentially dangerous latex formula]
[unparseable or potentially dangerous latex formula]
[unparseable or potentially dangerous latex formula]
[unparseable or potentially dangerous latex formula]
Sequences A and B have 402 elements each, and the sums of their corresponding elements are 1206, 1207, 1208, 1209,..., 1606, 1607.
Sequences C and D have 401 elements each, and the sums of their corresponding elements are 1608, 1609, 1610, 1611,..., 2007, 2008.

Thus we have shown that there is a solution for k= [unparseable or potentially dangerous latex formula] and that for larger k no solution exists.

[88bobcat]

[sinkokuyou]

I got it fixed
also, someone did this:
For k pairs of number, the minimum sum of those 2k numbers are 1+2+3... +2k = 2k(2k+1)/2 = k(2k+1), since the sum of each pair has to be distinct and less than 2010, the maximum sum of the sums are 2009+2008+... + (2010-k) = (4019-k)k/2.

In order for k to be a valid one, we must have k(2k+1) <= (4019-k)k/2, which gives the max value of k=803