What is the maximum value f(n) of |s1 - s2| + |s2 - s3| + ... + |sn-1 - sn| over all permutations s1, s2, ... , sn of 1, 2, ... , n?
Solution
Answer: f(2m) = 2m2 - 1, f(2m+1) = 2m2 + 2m - 1.
In a maximal arrangement the terms must alternately increase and decrease. For suppose we have a < b < c or a > b > c, then |a - b| + |b - c| = |a - c|, so we can remove the middle term without affecting the sum. If we place it at one of the ends we must then increase the sum by at least 1. So suppose the peaks are p1, p2, ... and the troughs are t1 + t2 + ... . Then the sum is 2S pi - 2S ti + an end correction.
It is now convenient to look separately at n odd and n even. Suppose n = 2m. Then one of the ends must be a peak and the other a trough. Suppose p1 and t1 are at the ends. Then the end correction is -p1 + t1. So the maximum sum is achieved by taking the peaks to be {m+1, m+2, ... , 2m}, the troughs to be {1, 2, ... , m}, p1 to be m+1 and t1 to be m. The sum is then 2( (m+1) + (m+2) + ... + (m+m) ) - 2( 1 + 2 + ... + m) - 1 = 2m2 - 1. This is obviously maximal and easily achieved: just select elements alternately from {m+1, m+2 , ... , 2m} and {1, 2, ... , m}, taking care that the end points are m and m+1.
For n odd = 2m+1, we either have m+1 peaks and m troughs or vice versa. In the first case we must take the peaks as {m+1, ... , 2m+1}, the troughs as {1, 2, ... , m} and the two endpoints as m+1 and m+2. The sum is then 2( (m+1) + (m+2) + ... + (m+m+1) ) - 2(1 + 2 + ... + m) - (m+1) - (m+2) = 2m2 + 4m+2 - 2m - 3 = 2m2 + 2m - 1. If we have m peaks and m+1 troughs, then the peaks must be {m+2, ... , 2m+1}, the troughs {1, 2, ... , m+1}, and the end points m and m+1. The sum is then 2( (m+2) + (m+3) + ... + (m+m+1) ) - 2(1 + 2 + ... + m+1} + m + m+1 = 2m2 - 2 + 2m+1 = 2m2 + 2m - 1, which is the same.
© John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002