IMO 1997 SL 21

Origin: RUS

Problem

Let x1, x2, . . . , xn be real numbers satisfying the conditions |x1 + x2 + \cdot \cdot \cdot + xn| = 1 and |xi| \leqn + 1 for i = 1, 2, . . ., n. Show that there exists a permutation y1, . . . , yn of the sequence x1, . . . , xn such that |y1 + 2y2 + \cdot \cdot \cdot + nyn| \leqn + 1 .

Solution

For any permutation \pi = (y1, y2, . . . , yn) of (x1, x2, . . . , xn), denote by S(\pi) the sum y1 + 2y2 + \cdot \cdot \cdot + nyn. Suppose, contrary to the claim, that |S(\pi)| > n+1 for any \pi. Further, we note that if \pi′ is obtained from \pi by interchanging two neighboring elements, say yk and yk+1, then S(\pi) and S(\pi′) differ by |yk + yk+1| \leqn + 1, and consequently they must be of the same sign. Now consider the identity permutation \pi0 = (x1, . . . , xn) and the re- verse permutation \pi0 = (xn, . . . , x1). There is a sequence of permuta- tions \pi0, \pi1, . . . , \pim = \pi0 such that for each i, \pii+1 is obtained from \pii by interchanging two neighboring elements. Indeed, by successive in- terchanges we can put xn in the first place, then xn−1 in the second place, etc. Hence all S(\pi0), . . . , S(\pim) are of the same sign. However, since |S(\pi0) + S(\pim)| = (n + 1)|x1 + \cdot \cdot \cdot + xn| = n + 1, this implies that one of

S(\pi0) and S(\pi0) is smaller than n+1 in absolute value, contradicting the initial assumption.