Given x1, x2, ... , xn ∈ [0, 1], let s = S1≤i<j≤n |xi - xj|. Find f(n), the maximum value of s over all possible {xi}.
Solution
Answer: f(2m) = m2 (half the points 0, half 1); f(2m+1) = m2 + m (m+1 points 0, m points 1).
It remains to prove that we cannot do better than this. We prove that this is best possible by induction. It is obvious for n = 2, 3. Suppose it is true for n. Take n+2 points. Let A be the leftmost point and B the rightmost point. Then the new terms in the sum the n+2 points are AB and AC, CB for each existing C. But these 2n + 1 terms sum to at most n + 1 (AC + CB = AB ≤ 1). So f(n+2) ≤ f(n) + n + 1. For n = 2m this gives f(2m+2) ≤ m2 + 2m + 1 = (m + 1)2. For n = 2m + 1, it gives f(2m+3) ≤ m2 + m + 2m + 1 + 1 = (m+1)2 + (m+1).
© John Scholes
jscholes@kalva.demon.co.uk
15 Feb 2002