Problem 1499

Let $k$ be the number of possible pairs. Then the sum $S$ of the $2k$ numbers occurring in them can be estimated in two directions:
$S \geq 1+2+\ldots+2k = k(2k+1)$ (all numbers are different) and
$S \leq n+(n-1)+\ldots+(n-k+1) = nk - \frac{1}{2}k(k-1)$ (all sums are different and $\leq n$).
This yields for $n \geq 3$ because $k > 0$ after division by $k$ the inequality $2k+1 \leq n - \frac{1}{2}(k-1)$, from which $k \leq \frac{2n-1}{5}$ follows. Therefore, there are at most $\left\lfloor\frac{2n-1}{5}\right\rfloor$ possible pairs
($\lfloor x\rfloor$ denotes the greatest integer $\leq x$). For $n < 3$, it is obviously $k=0$.
Now we give a construction for $n \geq 3$ with exactly $\left\lfloor\frac{2n-1}{5}\right\rfloor$ pairs. For this, let $n=5m+3$, so $k=2m+1$. The following table shows the pairs and their sums, where for small $m$ some columns must be omitted due to ambiguity of the terms:

The $2m+1$ pairs contain all numbers from 1 to $4m+2$; their sums range from $3m+3$ to $5m+3$ and are clearly different and not greater than $n$.
The same construction works for $n=5m+4$ and $n=5m+5 \quad(m \geq 0)$, because here $k=2m+1$ again. For $n=5m+2$, $k=2m$ is sufficient. Therefore, the last column of the table can simply be omitted here. For $n=5m+1$, $k=2m$ as well, and we omit the last column of the table and also decrease each upper number in the first row by 1. Thus, all conditions are again satisfied.

Hint: Many participants were misled by the example to assume $k=\lfloor n / 3\rfloor$ as the maximum number. However, those who discovered the three(!) pairs (2;4), (1;6), (3;5) or (1;5), (3;4), (2;6) for $n=8$ were immune to this estimate. The rarely occurring misunderstanding of the formulation, "no common element" in the sense that pairs $(x; x)$ were allowed, led to a trivial problem, whose solution was only awarded a modest score.