Problem 3

Let $n$ be an integer greater than or equal to 1. Find, in terms of $n$, the smallest integer $k \geqslant 2$ such that, among $k$ real numbers, there necessarily exist two whose difference, in absolute value, is either strictly less than $1 / n$ or strictly greater than $n$.

## §
Solution

We will prove that $k=n^{2}+2$. Indeed, if $k \leqslant n^{2}+1$, consider the $k$ real numbers $0, 1 / n, 2 / n, \ldots$, $(k-1) / n$. The minimum distance between any two of these numbers is $1 / n$, and the maximum distance between any two of these numbers is $(k-1) / n$, which is less than or equal to $n$.

Now suppose that $k=n^{2}+2$. Let $x_{0}, x_{1}, \ldots, x_{k-1}$ be real numbers, sorted in ascending order, and let $s$ be the smallest possible difference between any two of these numbers. It can be shown by immediate induction that $x_{\ell} \geqslant x_{0}+\ell s$ for all integers $\ell \leqslant k-1$. Consequently, $x_{n^{2}+1} \geqslant x_{0} + (n^{2}+1)s$. Since $s$ is the smallest difference, $s$ must be strictly greater than $1/n$. Therefore, $(n^{2}+1)s$ is strictly greater than $n$.