Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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> \displaystyle x_1 , x_2 , \ldots , x_n </math> be real numbers satisfying <math> \displaystyle x_1^2 + x_2^2 + \cdots + x_n^2 = 1 </math>.  Prove that for every integer <math> \displaystyle k \ge 2 </math> there are integers <math> \displaystyle a_1, a_2, \ldots a_n </math>, not all 0, such that <math> \displaystyle | a_i | \le k-1 </math> for all <math> \displaystyle i </math> and
+
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.
  
−
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>\displaystyle b_i </math> is a non-negative integer less than <math>\displaystyle k</math>, fall in the interval <math> \displaystyle [ 0 , (k-1)\sqrt{n} ] </math>.  We may partition this interval into <math> \displaystyle k^n - 1 </math> subintervals of length <math> \frac{ (k-1)\sqrt{n} }{k^n - 1} </math>. But since there are <math> \displaystyle 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}}
  
−
== Resources ==
+
{{IMO box|num-b=2|num-a=4|year=1987}}
−
 
 
−
* [[1987 IMO Problems]]
 
−
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366536#p366536 Discussion on AoPS/MathLinks]
 
−
 
 
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1987_IMO_Problems/Problem_3&oldid=193616"