IMO 1987 SL 15

Origin: FRG

Problem

Suppose x1, x2, . . . , xn are real numbers with x2 1 + x2 2 + \cdot \cdot \cdot + x2 n = 1. Prove that for any integer k > 1 there are integers ei not all 0 and with |ei| < k such that |e1x1 + e2x2 + \cdot \cdot \cdot + enxn| \leq(k −1)\sqrtn kn −1 .

Solution

Since x2 1 + x2 2 + \cdot \cdot \cdot + x2 n = 1, we get by the Cauchy-Schwarz inequality |x1| + |x2| + \cdot \cdot \cdot + |xn| \leq

n(x2 1 + x2 2 + \cdot \cdot \cdot + x2n) = \sqrtn. Hence all kn sums of the form e1x1 + e2x2 + \cdot \cdot \cdot + enxn, with ei \in {0, 1, 2, . . ., k −1}, must lie in some closed interval ℑof length (k −1)\sqrtn. This interval can be covered with kn −1 closed subintervals of length k−1 kn−1 \sqrtn. By the pigeonhole principle there must be two of these sums

lying in the same subinterval. Their difference, which is of the form e1x1 + e2x2 + \cdot \cdot \cdot + enxn where ei \in{0, \pm1, . . ., \pm(k −1)}, satisfies |e1x1 + e2x2 + \cdot \cdot \cdot + enxn| \leq(k −1)\sqrtn kn −1 .