IMO 1987/A3 solution

IMO 1987

Problem A3

Let x₁, x₂, ... , x_n be real numbers satisfying x₁² + x₂² + ... + x_n² = 1. Prove that for every integer k ≥ 2 there are integers a₁, a₂, ... , a_n, not all zero, such that |a_i| ≤ k - 1 for all i, and |a₁x₁ + a₂x₂ + ... + a_nx_n| ≤ (k - 1)√n/(kⁿ - 1).

Solution

This is an application of the pigeon-hole principle.

Assume first that all x_i are non-negative. Observe that the sum of the x_i is at most √n. [This is a well-known variant, (∑_1≤i≤n x_i)² ≤ n ∑_1≤i≤n x_i², of the AM-GM result. See, for example, Arthur Engel, Problem Solving Strategies, Springer 1998, p163, ISBN 0387982191].

Consider the kⁿ possible values of ∑_1≤i≤n b_ix_i, where each b_i is an integer in the range [0,k-1]. Each value must lie in the interval [0, k-1 √n]. Divide this into kⁿ-1 equal subintervals. Two values must lie in the same subinterval. Take their difference. Its coefficients are the required a_i. Finally, if any x_i are negative, solve for the absolute values and then flip signs in the a_i.

Comment

This solution is due to Gerhard Woeginger, email 24 Aug 99.

Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

28th IMO 1987