AoPSWiki
Want to learn how to tackle those tough AMC/AIME/Olympiad counting and probability problems? Check out Art of Problem Solving's Intermediate Counting & Probability by David Patrick.

1987 IMO Problems/Problem 3

From AoPSWiki

Revision as of 00:49, 26 October 2007 by Temperal (Talk | contribs)
(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)

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)
Preceded by
Problem 2 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 4
Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/1987_IMO_Problems/Problem_3"
Want to learn how to tackle those tough AMC/AIME/Olympiad counting and probability problems? Check out Art of Problem Solving's Intermediate Counting & Probability by David Patrick.
© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us