Auswahlklausur

Solution:

Let $k$ be the number of possible pairs. Then the sum $S$ of the $2 k$ numbers occurring in them can be estimated in two directions:

$S \geq 1+2+\ldots+2 k = k(2 k+1)$ (all numbers are distinct) and

$S \leq n+(n-1)+\ldots+(n-k+1) = n k - \frac{1}{2} k(k-1)$ (all sums are distinct and $\leq n$).

For $n \geq 3$, since $k>0$, this yields, after dividing by $k$, the inequality $2 k+1 \leq n - \frac{1}{2}(k-1)$, from which $k \leq \frac{2 n-1}{5}$ follows. Hence there are at most $\left\lfloor\frac{2 n-1}{5}\right\rfloor$ possible pairs
($\lfloor x\rfloor$ denotes the largest integer $\leq x$). For $n<3$ it is obvious that $k=0$.

Now, for $n \geq 3$, we give a construction with exactly $\left\lfloor\frac{2 n-1}{5}\right\rfloor$ pairs. For this, let first $n=5 m+3$, so $k=2 m+1$. The following table shows the pairs and their sums, where for small $m$ some columns must be struck out because of ambiguity of the terms:

The same construction also works for $n=5 m+4$ and $n=5 m+5$ $(m \geq 0)$, because here again $k=2 m+1$. For $n=5 m+2$, $k=2 m$ suffices. Therefore, in this case the last column of the table can simply be omitted. For $n=5 m+1$, likewise $k=2 m$, and we again omit the last column of the table and, in addition, decrease every upper number in the first row by $1$. In this way all conditions are again satisfied.