11th Balkan 1994 Problem 3 What is the maximum value f(n) of |s 1 - s 2 | + |s 2 - s 3 | + ... + |s n-1 - s n | over all permutations s 1 , s 2 , ... , s n of 1, 2, ... , n? Solution
: f(2m) = 2m 2 - 1, f(2m+1) = 2m 2 + 2m - 1. In a maximal arrangement the terms must alternately increase and decrease. For suppose we have 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 p 1 , p 2 , ... and the troughs are t 1 + t 2 + ... . Then the sum is 2 S p i - 2 S t i + 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 p 1 and t 1 are at the ends. Then the end correction is -p 1 + t 1 . So the maximum sum is achieved by taking the peaks to be {m+1, m+2, ... , 2m}, the troughs to be {1, 2, ... , m}, p 1 to be m+1 and t 1 to be m. The sum is then 2( (m+1) + (m+2) + ... + (m+m) ) - 2( 1 + 2 + ... + m) - 1 = 2m 2 - 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) = 2m 2 + 4m+2 - 2m - 3 = 2m 2 + 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 = 2m 2 - 2 + 2m+1 = 2m 2 + 2m - 1, which is the same. 11th Balkan 1994 © John Scholes jscholes@kalva.demon.co.uk 11 Apr 2002