(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**

Answer: (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?]

© John Scholes

jscholes@kalva.demon.co.uk

12 Dec 1998