MHB What is the maximum sum of products of consecutive integers from 1 to n?

[Ackbach]

Here is this week's POTW:

-----

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.
\]

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 226 - Jul 27, 2016

This was Problem B-3 in the 1996 William Lowell Putnam Mathematical Competition.

No one answered this week's POTW. The solution, attributed to Kiran Kedlaya and his associates, follows:

Spoiler

View $x_1, \dots, x_n$ as an arrangement of the numbers $1, 2, \dots,n$ on a circle. We prove that the optimal arrangement is
\[
\dots, n-4, n-2, n, n-1, n-3, \dots
\]
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:
\[
\dots, a_{n-4}, a_{n-2}, a_n = n, a_{n-1}, a_{n-3}, \dots
\]
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} > \dots > a_1$ and so $a_k = k$ for $k = 1, 2, \dots, n$, i.e. that the optimal arrangement is as claimed. In particular, the maximum value of the sum is
\begin{aligned}
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}.
\end{aligned}