1987 IMO Problems/Problem 3

Revision as of 20:49, 25 October 2007 by Temperal (talk | contribs) (template)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)


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 }$.


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
Invalid username
Login to AoPS