1987 IMO Problems/Problem 3

Problem

Let $\displaystyle x_1 , x_2 , \ldots , x_n$ be real numbers satisfying $\displaystyle x_1^2 + x_2^2 + \cdots + x_n^2 = 1$ . Prove that for every integer $\displaystyle k \ge 2$ there are integers $\displaystyle a_1, a_2, \ldots a_n$ , not all 0, such that $\displaystyle | a_i | \le k-1$ for all $\displaystyle i$ and

$|a_1x_1 + a_2x_2 + \cdots + a_nx_n| \le \frac{ (k-1) \sqrt{n} }{ k^n - 1 }$ .

Solution

We first note that by the Power Mean Inequality, $\sum_{i=1}^{n} x_i \le \sqrt{n}$ . Therefore all sums of the form $\sum_{i=1}^{n} b_i x_i$ , where the $\displaystyle b_i$ is a non-negative integer less than $\displaystyle k$ , fall in the interval $\displaystyle [ 0 , (k-1)\sqrt{n} ]$ . We may partition this interval into $\displaystyle k^n - 1$ subintervals of length $\frac{ (k-1)\sqrt{n} }{k^n - 1}$ . But since there are $\displaystyle k^n$ such sums, by the pigeonhole principle, two must fall into the same subinterval. It is easy to see that their difference will form a sum with the desired properties.