IMO 2012 Shortlist C2
Let n ≥ 1 be an integer. What is the maximum number of disjoint pairs of elements of the set {1,2,...,n} such that the s...
Category: Combinatorics
Problem
Let n ≥ 1 be an integer. What is the maximum number of disjoint pairs of elements of the set {1,2,...,n} such that the sums of the different pairs are different integers not exceeding n? Solution. Consider x such pairs in {1,2,...,n}. The sum S of the 2x numbers in them is at least 1+2+···+2x since the pairs are disjoint. On the other hand S ≤ n+(n−1)+···+(n−x+1) because the sums of the pairs are different and do not exceed n. This gives the inequality 2x(2x + 1) ≤ nx − x(x − 1) , which leads to x ≤ 2n−1 . Hence there are at most 2n−1 pairs with the given properties. We show a construction with exactly 2n−1 pairs. First consider the case n = 5k + 3 with k ≥ 0, where 2n−1 = 2k + 1. The pairs are displayed in the following table. Pairs 3k + 1 3k ··· 2k + 2 4k + 2 4k + 1 ··· 3k + 3 3k + 2 2 4 ··· 2k 1 3 ··· 2k − 1 2k + 1 Sums 3k + 3 3k + 4 ··· 4k + 2 4k + 3 4k + 4 ··· 5k + 2 5k + 3 The 2k+1 pairs involve all numbers from 1 to 4k+2; their sums are all numbers from 3k+3 to 5k + 3. The same construction works for n = 5k + 4 and n = 5k + 5 with k ≥ 0. In these cases the required number 2n−1 of pairs equals 2k + 1 again, and the numbers in the table do not exceed 5k + 3. In the case n = 5k + 2 with k ≥ 0 one needs only 2k pairs. They can be obtained by ignoring the last column of the table (thus removing 5k + 3). Finally, 2k pairs are also needed for the case n = 5k + 1 with k ≥ 0. Now it suffices to ignore the last column of the table and then subtract 1 from each number in the first row. Comment. The construction above is not unique. For instance, the following table shows another set of 2k + 1 pairs for the cases n = 5k + 3, n = 5k + 4, and n = 5k + 5. Pairs 1 2 ··· k k + 1 k + 2 ··· 2k + 1 4k + 1 4k − 1 ··· 2k + 3 4k + 2 4k ··· 2k + 2 Sums 4k + 2 4k + 1 ··· 3k + 3 5k + 3 5k + 2 ··· 4k + 3 The table for the case n = 5k + 2 would be the same, with the pair (k + 1,4k + 2) removed. For the case n = 5k + 1 remove the last column and subtract 2 from each number in the second row. 21