Problem:
From the set of integers {1,2,3,…,2009}, choose k pairs {ai​,bi​} with ai​<bi​ so that no two pairs have a common element. Suppose that all the sums ai​+bi​ are distinct and less than or equal to 2009. Find the maximum possible value of k.
Solution:
Let the pairs be (ai​,bi​) for i=1,2,3,…,k, and set S=∑i=1k​(ai​+bi​).
From the given conditions, it follows that 1+2+⋯+2k≤S≤2009+ 2008+⋯+(2010−k), giving k(2k+1)≤21​k(4019−k). Solving this inequality for k yields k≤54017​, and therefore k cannot exceed 803​. This value of 803 can be achieved by choosing pairs (1,1207),(2,1208),…, (401,1607),(402,805),…,(803,1206).
The problems on this page are the property of the MAA's American Mathematics Competitions