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"

 
(template)
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 11: Line 11:
 
== Solution ==
 
== Solution ==
  
−
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.
+
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.
  
 
{{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]]

Revision as of 19:49, 25 October 2007

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

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