Putnam 1996 Problem B3 (x 1 , x 2 , ... , x n ) is a permutation of (1, 2, ... , n). What is the maximum of x 1 x 2 + x 2 x 3 + ... + x n-1 x n + x n x 1 ? Solution
: (2n 3 + 3n 2 - 11n + 18)/6. Easy. For n = 2, the maximum is simply 1.2 + 2.1 = 4. If we take an arrangement for {1, 2, ... , n-1} and insert n between i and j then the net increase in the sum is n(i + j) - ij. This is an increasing function of i [ = (n - j)i + nj ] and of j, so its maximum value is n 2 - 2, achieved if n is inserted between (n - 1) and (n - 2). Of course, this might not be possible for a particular arrangement of {1, 2, ... , n-1}, but it shows that the maximum value for n elements is at most 4 + (3 2 - 2) + (4 2 - 2) + ... + (n 2 - 2) = n(n + 1)(n + 2)/6 - 2(n - 1) + 1 = (2n 3 + 3n 2 - 11n + 18)/6. This can actually be achieved by repeatedly inserting n between the two maximum elements. That puts the two new maximum elements together ready for the next insertion. [Definitely no extra credit for checking this explicitly! You find the arrangement can be written as {2, 4, 6, ... , 2[n/2], 2[(n-1]/2]+1, 2[(n-1]/2]-1, ... , 5, 3, 1 - the even elements in increasing sequence followed by the odd elements in decreasing sequence. For n = 2m, this gives 4(1.2 + 2.3 + ... + (m-1)m) + 2m(2m-1) + (1.3 + 3.5 + ... + (2m-3)(2m-1) ) + 2.1 = 4/3 (m-1)m(m+1) + 2m(2m-1) + 1/3 (m-1)(4n 2 - 2m - 3) + 2 = 1/3 (8m 3 + 6m 2 - 11m + 9), as required, and similarly for n odd. But why go through all that rigmarole?] Putnam 1996 © John Scholes jscholes@kalva.demon.co.uk 12 Dec 1998