Problem 758

: min 2n - 2, max [n 2 /2]. The minimum is obviously 2(n-1). The difference between 1 and n is n-1 and the sum of the signed differences as we go from n to 1 either way round the circle must be n-1. The sum of the unsigned differences must be at least as large, so S ≥ 2(n-1). This is achieved by the order 1, 2, 3, ... , n. The maximum is almost obvious. If the numbers are a 1 , a 2 , ... , a n . Then each difference is a i+1 - a i or - a i+1 + a i . So the total of all the differences is k 1 a 1 + k 2 a 2 + ... + k n a n , where each k i is -2, 0 or 2 and their sum is 0. So permuting back to 1, 2, ... , n the sum is h 1 + 2h 2 + 3h 3 + ... + nh n , where each h i is 0 or ±2 and the sum of the h i is 0. If n = 2m, this is maximised by taking h 1 = h 2 = ... = h m = -2 and h m+1 = ... = h 2m = 2, giving a sum of 2m 2 . If n = 2m+1, it is maximised by taking h 1 = ... = h m = -2, h m+1 = 0, h m+2 = ... = h 2m+1 = 2, giving a sum of 2m(m+1). Checking that this can be achieved, we take: 1, 2m, 2, 2m-1, 3, 2m-2, ... , m-1, m+2, m, m+1 in the even case and 1, 2m+1, 2, 2m-1, 3, 2m-3, ... , m-1, m+3, m, m+2, m+1 in the odd case. 37th BMO 2001 © John Scholes [email protected] 18 Jul 2002