Let x1 ≥ x2 ≥ ... ≥ xn, and y1 ≥ y2 ≥ ... ≥ yn be real numbers. Prove that if zi is any permutation of the yi, then:
∑1n (xi - yi)2 ≤ ∑1n (xi - zi)2.
Solution
If x ≥ x' and y ≥ y', then (x - y)2 + (x' - y')2 ≤ (x - y')2 + (x' - y)2. Hence if i < j, but zi ≤ zj, then swapping zi and zj reduces the sum of the squares. But we can return the order of the zi to yi by a sequence of swaps of this type: first swap 1 to the 1st place, then 2 to the 2nd place and so on.
Solutions are also available in: Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
11 Oct 1998