6th CanMO 1974 Problem 4 What is the maximum possible value for the sum of the absolute values of the differences between each pair of n non-negative real numbers which do not exceed 1?
Let the numbers be x 1 >= x 2 >= ... >= x n . Then the sum is (x 1 - x 2 ) + (x 1 - x 3 ) + ... + (x 1 - x n ) + (x 2 - x 3 ) + ... + (x 2 - x n ) + (x 3 - x 4 ) + ... + (x 3 - x n ) + ... + (x n-1 - x n ) = (n-1) x 1 + (n-2) x 2 + (n-3) x 3 + ... + x n-1 - (n- 1) x n - (n-2) x n-1 - ... - x 2 = (n-1) x 1 + (n-3) x 2 + (n-5) x 3 + ... + (n - (2n-1)) x n . Since all x i are non-negative we maximise the sum by taking the x i with non-positive coefficients to be zero and the x i with positive coefficients to be 1. That gives the maximum M = (n-1) + (n-3) + (n-5) + ... . If n = 2m, then M = 1 + 3 + 5 + ... + 2m-1 = m 2 . If n = 2m+1, then M = 2 + 4 + ... + 2m = m(m+1). We can combine that into a single formula as M = [n 2 /4]. 6th CanMO 1974 © John Scholes jscholes@kalva.demon.co.uk 10 June 2002