Difference between revisions of "2009 AIME II Problems/Problem 12"
m (→Solution) |
|||
| 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. | ||
Latest revision as of 19:56, 4 June 2020
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 • 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. 
