Difference between revisions of "1987 IMO Problems/Problem 3"

Latest revision as of 03:36, 28 May 2023

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

@@ Line 14: / Line 14: @@
 === Solution 2 ===
-This Solution is very similar to solution 1 but uses a slightly different approach for the first part. It suffices to find <math>{a_i}</math> where <math>a_i</math> is positive. Let <math>f(a_1, a_2, ..., a_n) = a_1| x_1|+a_2 |x_2|+\cdots+a_n |x_n|\geq0</math>.
+This solution is very similar to Solution 1 but uses a slightly different approach for the first part. It suffices to find <math>{a_i}</math> where <math>a_i</math> is positive. Let <math>f(a_1, a_2, ..., a_n) = a_1| x_1|+a_2 |x_2|+\cdots+a_n |x_n|\geq0</math>.
 By the [[Cauchy-Schwarz Inequality]],
 <cmath>\begin{split}

Page

Toolbox

Search