Let x1, x2, ... , xn be real numbers satisfying |x1 + x2 + ... + xn| = 1 and |xi| ≤ (n+1)/2 for all i. Show that there exists a permutation yi of xi such that |y1 + 2y2 + ... + nyn| ≤ (n+1)/2.
Solution
Without loss of generality we may assume x1 + ... + xn = +1. [If not just reverse the sign of every xi.] For any given arrangement xi we use sum to mean x1 + 2x2 + 3x3 + ... + nxn. Now if we add together the sums for x1, x2, ... , xn and the reverse xn, xn-1, ... , x1, we get (n+1)(x1 + ... + xn) = n+1. So either we are home with the original arrangement or its reverse, or they have sums of opposite sign, one greater than (n+1)/2 and one less than -(n+1)/2.
A transposition changes the sum from ka + (k+1)b + other terms to kb + (k+1)a + other terms. Hence it changes the sum by |a - b| (where a, b are two of the xi) which does not exceed n+1. Now we can get from the original arrangement to its reverse by a sequence of transpositions. Hence at some point in this sequence the sum must fall in the interval [-(n+1)/2, (n+1)/2] (because to get from a point below it to a point above it in a single step requires a jump of more than n+1). That point gives us the required permutation.
© John Scholes
jscholes@kalva.demon.co.uk
22 Oct 1998
Last corrected/updated 21 Aug 03