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

Solution 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.

Solution 2

This solution is very similar to Solution 1 but uses a slightly different approach for the first part. It suffices to find ${a_i}$ where $a_i$ is positive. Let $f(a_1, a_2, ..., a_n) = a_1| x_1|+a_2 |x_2|+\cdots+a_n |x_n|\geq0$. By the Cauchy-Schwarz Inequality, \[\begin{split} \left(a_1 x_1+a_2 x_2+...+a_n x_n\right)^2  &\leq \left(a_1^2+a_2^2+...+a_n^2\right)\cdot\left(x_1^2+x_2^2+...+x_n^2\right) \\ &=a_1^2+a_2^2+...+a_n^2 \\ &\leq n(k-1)^2 \end{split}\] This implies that $\left(a_1 x_1+a_2 x_2+...+a_n x_n\right)^2\leq \sqrt{n} (k-1)$, and hence the codomain of $f(a_1, a_2, ..., a_n)$ is $\left[0, \sqrt{n} (k-1)\right]$. The rest of the proof is similar to Solution 1.

~Iraevid13

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