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)≤21k(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