Contest Math sum Partition question

Question

From IMO 2012 shortlist:

What is the maximum value of $k$ such that the set $S=\{1,2,\cdots,2018\}$ can be partitioned into $k$ disjoint pairs such that the sum of (the two numbers in) each pair is pairwise distinct and none of the sums exceeds $2018$.

I predict that the answer is $672$, that is when the pairs are $(1,2017),(2,2015),(3,2013),\cdots,(672,675)$. But I am not sure whether my prediction is right. Furthermore, I wanted to try proving that $673$ pairs is impossible, and I think some pigeonhole principle might be needed but I don't know how to make use of it. Any help is surely appreciated. Thanks!

N.B : If anyone got a solution without using the pigeonhole principle, that would be fine too!

Answer 1

This problem is in IMO 2012 shortlist, page 20. The answer is $\left\lfloor \frac{2n-1}{5}\right\rfloor$. In this case $807$.

Original post in the shortlist:

C2. Let $n \geqslant 1$ be an integer. What is the maximum number of disjoint pairs of elements of the set $\{1,2, \ldots, n\}$ such that the sums of the different pairs are different integers not exceeding $n ?$ Solution. Consider $x$ such pairs in $\{1,2, \ldots, n\} .$ The sum $S$ of the $2 x$ numbers in them is at least $1+2+\cdots+2 x$ since the pairs are disjoint. On the other hand $S \leqslant n+(n-1)+\cdots+(n-x+1)$ because the sums of the pairs are different and do not exceed $n$. This gives the inequality $$\frac{2 x(2 x+1)}{2} \leqslant n x-\frac{x(x-1)}{2}$$ which leads to $x \leqslant \frac{2 n-1}{5}$. Hence there are at most $\left\lfloor\frac{2 n-1}{5}\right\rfloor$ pairs with the given properties. We show a construction with exactly $\left\lfloor\frac{2 n-1}{5}\right\rfloor$ pairs. First consider the case $n=5 k+3$ with $k \geqslant 0,$ where $\left\lfloor\frac{2 n-1}{5}\right\rfloor=2 k+1 .$ The pairs are displayed in the following table.

$$\begin{array}{|c|c|c|c|} \hline \text{pairs}& 3k+1 & 3k &\cdots&2k+2&4k+2&4k+1&\cdots&3k+3&3k+2 \\ &2 & 4& \cdots&2k&1&3&\cdots&2k-1&2k+1\\ \hline \text{sums} &3k+3 &3k+4&\cdots&4k+2&4k+3&4k+4&\cdots&5k+2&5k+3\\ \hline \end{array}$$ The $2 k+1$ pairs involve all numbers from 1 to $4 k+2 ;$ their sums are all numbers from $3 k+3$ to $5 k+3 .$ The same construction works for $n=5 k+4$ and $n=5 k+5$ with $k \geqslant 0 .$ In these cases the required number $\left\lfloor\frac{2 n-1}{5}\right\rfloor$ of pairs equals $2 k+1$ again, and the numbers in the table do not exceed $5 k+3 .$ In the case $n=5 k+2$ with $k \geqslant 0$ one needs only $2 k$ pairs. They can be obtained by ignoring the last column of the table (thus removing $5 k+3$ ). Finally, $2 k$ pairs are also needed for the case $n=5 k+1$ with $k \geqslant 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 $2 k+1$ pairs for the cases $n=5 k+3, n=5 k+4,$ and $n=5 k+5$ \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline \text{Pairs } & 1 & 2 & \cdots & k & k+1 & k+2 & \cdots & 2k+1\\ & 4k+1 & 4k-1 & \cdots & 2k+3 & 4k+2 & 4k & \cdots & 2k+2\\ \hline \text{Sums} & 4k+2& 4k+1 & \cdots & 3k+3 & 5k+3& 5k+2 & \cdots & 4k+3\\ \hline \end{array} The table for the case $n=5 k+2$ would be the same, with the pair $(k+1,4 k+2)$ removed. For the case $n=5 k+1$ remove the last column and subtract 2 from each number in the second row.