Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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)/2</math>.
+
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)/2 \geq k(2k+1)</math>. As <math>k</math> is positive, this simplifies to <math>(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>.
+
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.  

Revision as of 18:56, 4 June 2020

Problem

From the set of integers $\{1,2,3,\dots,2009\}$, choose $k$ pairs $\{a_i,b_i\}$ with $a_i<b_i$ so that no two pairs have a common element. Suppose that all the sums $a_i+b_i$ are distinct and less than or equal to $2009$. Find the maximum possible value of $k$.

Solution

Suppose that we have a valid solution with $k$ pairs. As all $a_i$ and $b_i$ are distinct, their sum is at least $1+2+3+\cdots+2k=k(2k+1)$. On the other hand, as the sum of each pair is distinct and at most equal to $2009$, the sum of all $a_i$ and $b_i$ is at most $2009 + (2009-1) + \cdots + (2009-(k-1)) = \frac{k(4019-k)}{2}$.

Hence we get a necessary condition on $k$: For a solution to exist, we must have $\frac{k(4019-k)}{2} \geq k(2k+1)$. As $k$ is positive, this simplifies to $\frac{4019-k}{2} \geq 2k+1$, whence $5k\leq 4017$, and as $k$ is an integer, we have $k\leq \lfloor 4017/5\rfloor = 803$.

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 $2\cdot 803 = 1606$. When using these numbers, the average sum will be $1607$. Hence we can try looking for a nice systematic solution that achieves all sums between $1607-401=1206$ and $1607+401=2008$, inclusive.

Such a solution indeed does exist, here is one:

Partition the numbers $1$ to $1606$ into four sequences:

  • $A=1,3,5,7,\dots,801,803$
  • $B=1205,1204,1203,1202,\dots,805,804$
  • $C=2,4,6,8,\dots,800,802$
  • $D=1606,1605,1604,1603,\dots,1207,1206$

Sequences $A$ and $B$ have $402$ elements each, and the sums of their corresponding elements are $1206,1207,1208,1209,\dots,1606,1607$. Sequences $C$ and $D$ have $401$ elements each, and the sums of their corresponding elements are $1608,1609,1610,1611,\dots,2007,2008$.

Thus we have shown that there is a solution for $k=\boxed{803}$ and that for larger $k$ 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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_II_Problems/Problem_12&oldid=123738"