Difference between revisions of "1987 IMO Problems/Problem 3"
m (→Solution 2) |
|||
(2 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | Let <math> | + | Let <math>x_1 , x_2 , \ldots , x_n </math> be real numbers satisfying <math>x_1^2 + x_2^2 + \cdots + x_n^2 = 1 </math>. Prove that for every integer <math>k \ge 2 </math> there are integers <math>a_1, a_2, \ldots a_n </math>, not all 0, such that <math>| a_i | \le k-1 </math> for all <math>i </math> and |
<center> | <center> | ||
Line 10: | Line 10: | ||
== Solution == | == Solution == | ||
+ | === Solution 1 === | ||
+ | We first note that by the [[Power Mean Inequality]], <math> \sum_{i=1}^{n} x_i \le \sqrt{n} </math>. Therefore all sums of the form <math> \sum_{i=1}^{n} b_i x_i </math>, where the <math>b_i </math> is a non-negative integer less than <math>k</math>, fall in the interval <math>[ 0 , (k-1)\sqrt{n} ] </math>. We may partition this interval into <math>k^n - 1 </math> subintervals of length <math> \frac{ (k-1)\sqrt{n} }{k^n - 1} </math>. But since there are <math>k^n </math> 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 <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} | ||
+ | \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}</cmath> | ||
+ | This implies that <math>\left(a_1 x_1+a_2 x_2+...+a_n x_n\right)^2\leq \sqrt{n} (k-1)</math>, and hence the codomain of <math>f(a_1, a_2, ..., a_n)</math> is <math>\left[0, \sqrt{n} (k-1)\right]</math>. The rest of the proof is similar to Solution 1. | ||
+ | |||
+ | ~[[User:Iraevid13|Iraevid13]] | ||
{{alternate solutions}} | {{alternate solutions}} | ||
− | == | + | {{IMO box|num-b=2|num-a=4|year=1987}} |
− | |||
− | |||
− | |||
− | |||
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] |
Latest revision as of 04:36, 28 May 2023
Contents
Problem
Let be real numbers satisfying
. Prove that for every integer
there are integers
, not all 0, such that
for all
and
.
Solution
Solution 1
We first note that by the Power Mean Inequality, . Therefore all sums of the form
, where the
is a non-negative integer less than
, fall in the interval
. We may partition this interval into
subintervals of length
. But since there are
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 where
is positive. Let
.
By the Cauchy-Schwarz Inequality,
This implies that
, and hence the codomain of
is
. The rest of the proof is similar to Solution 1.
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 |