Problem (Combinatorics):
Let $n \geq 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 \leq 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} \leq n x-\frac{x(x-1)}{2}
$$

which leads to $x \leq \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 \geq 0$, where $\left\lfloor\frac{2 n-1}{5}\right\rfloor=2 k+1$. The pairs are displayed in the following table.

| Pairs | $3 k+1$ | $3 k$ | $\cdots$ | $2 k+2$ | $4 k+2$ | $4 k+1$ | $\cdots$ | $3 k+3$ | $3 k+2$ |
| :--- | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
|  | 2 | 4 | $\cdots$ | $2 k$ | 1 | 3 | $\cdots$ | $2 k-1$ | $2 k+1$ |
| Sums | $3 k+3$ | $3 k+4$ | $\cdots$ | $4 k+2$ | $4 k+3$ | $4 k+4$ | $\cdots$ | $5 k+2$ | $5 k+3$ |

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 \geq 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 \geq 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 \geq 0$. Now it suffices to ignore the last column of the table and then subtract 1 from each number in the first row.

Final answer: $\lfloor\frac{2 n-1}{5}\rfloor$