Putnam 1996, Problem B-3

Given that \( \{x_1, x_2, \ldots, x_n\} = \{1,2,\ldots,n\} \), find, with proof, the largest possible value, as a function of \( n \) (with \( n \geq 2 \)), of  
\[
x_1x_2 + x_2x_3 + \cdots + x_{n-1}x_n + x_nx_1.
\]

Solution:
View \(x_1, \ldots, x_n\) as an arrangement of the numbers \(1, 2, \ldots, n\) on a circle. We prove that the optimal arrangement is  
\[
\ldots, n - 4, n - 2, n, n, n - 1, n - 3, \ldots
\]  

To show this, note that if \(a, b\) is a pair of adjacent numbers and \(c, d\) is another pair (read in the same order around the circle) with \(a < d\) and \(b > c\), then the segment from \(b\) to \(c\) can be reversed, increasing the sum by  
\[
ac + bd - ab - cd = (d - a)(b - c) > 0.
\]  

Now relabel the numbers so they appear in order as follows:  
\[
\ldots, a_{n-4}, a_{n-2}, a_n = n, a_{n-1}, a_{n-3}, \ldots
\]  
where without loss of generality we assume \(a_{n-1} > a_{n-2}\). By considering the pairs \(a_{n-2}, a_n\) and \(a_{n-1}, a_{n-3}\) and using the trivial fact \(a_n > a_{n-1}\), we deduce \(a_{n-2} > a_{n-3}\). We then compare the pairs \(a_{n-4}, a_{n-2}\) and \(a_{n-1}, a_{n-3}\), and using that \(a_{n-1} > a_{n-2}\), we deduce \(a_{n-3} > a_{n-4}\). Continuing in this fashion, we prove that \(a_n > a_{n-1} > \cdots > a_1\) and so \(a_k = k\) for \(k = 1, 2, \ldots, n\), i.e. that the optimal arrangement is as claimed. In particular, the maximum value of the sum is  
\[
1 \cdot 2 + (n - 1) \cdot n + 1 \cdot 3 + 2 \cdot 4 + \cdots + (n - 2) \cdot n = 2 + n^2 - n + (1^2 - 1) + \cdots + [(n - 1)^2 - 1] = n^2 - n + 2 - (n - 1) + \frac{(n - 1)n(2n - 1)}{6} = \frac{2n^3 + 3n^2 - 11n + 18}{6}.
\]  

Alternate solution: We prove by induction that the value given above is an upper bound; it is clearly a lower bound because of the arrangement given above. Assume this is the case for \(n - 1\). The optimal arrangement for \(n\) is obtained from some arrangement for \(n - 1\) by inserting \(n\) between some pair \(x, y\) of adjacent terms. This operation increases the sum by \(nx + ny - xy = n^2 - (n - x)(n - y)\), which is an increasing function of both \(x\) and \(y\). In particular, this difference is maximal when \(x\) and \(y\) equal \(n - 1\) and \(n - 2\). Fortunately, this yields precisely the difference between the claimed upper bound for \(n\) and the assumed upper bound for \(n - 1\), completing the induction.