1987 IMO Problems/Problem 3

Problem

Let $x_1 , x_2 , \ldots , x_n$ be real numbers satisfying $x_1^2 + x_2^2 + \cdots + x_n^2 = 1$ . Prove that for every integer $k \ge 2$ there are integers $a_1, a_2, \ldots a_n$ , not all 0, such that $| a_i | \le k-1$ for all $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 $b_i$ is a non-negative integer less than $k$ , fall in the interval $[ 0 , (k-1)\sqrt{n} ]$ . We may partition this interval into $k^n - 1$ subintervals of length $\frac{ (k-1)\sqrt{n} }{k^n - 1}$ . But since there are $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.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

1987 IMO (Problems) • Resources
Preceded by Problem 2	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 4
All IMO Problems and Solutions

Page

Toolbox

Search

1987 IMO Problems/Problem 3

Problem

Solution