(x1, x2, ... , xn) is a permutation of (1, 2, ... , n). What is the maximum of x1x2 + x2x3 + ... + xn-1xn + xnx1?
Solution
Answer: (2n3 + 3n2 - 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 n2 - 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 + (32 - 2) + (42 - 2) + ... + (n2 - 2) = n(n + 1)(n + 2)/6 - 2(n - 1) + 1 = (2n3 + 3n2 - 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)(4n2 - 2m - 3) + 2 = 1/3 (8m3 + 6m2 - 11m + 9), as required, and similarly for n odd. But why go through all that rigmarole?]
© John Scholes
jscholes@kalva.demon.co.uk
12 Dec 1998