# Maximizing an unusual function (Putnam 1996)

“Fish," he said, "I love you and respect you very much. But I will kill you dead before this day ends.”

-- Ernest Hemingway, The Old Man and the Sea

I have, with varying degrees of concentration, been trying to resolve this problem for most of this evening:

If we require $\{a_1, a_2, ... a_n \} = \{1, 2, ... n\}$, determine the maximum value of $a_1 a_2 + a_2 a_3 + \dots + a_{n-1}a_n + a_n a_1$ as a function of $n$.

(That is, how can we - by permuting the first $n$ positive integers to form a sequence $\{a_n\}$ - maximize the expression above for arbitrary $n$?)

My thinking was that the fundamental difficulty with the problem was the lack of symmetry. So, my approach below was motivated by trying to introduce some.

Notice that $\sum_{k = 1}^n a_k^2 = \sum_{k = 1}^n k^2$, regardless of what the sequence $\{a_k\}$ is. Now, we do a neat rearrangement by completing the squares. (In the first and second lines, we are just adjusting the sigma notation.) If $S$ is our original expression,

\begin{eqnarray} 2 \sum_{k = 1}^n a_k^2 - 2S = 2 \sum_{k = 1}^n a_k^2 - 2 (a_1 a_2 + a_2 a_3 + \dots + a_{n-1}a_n + a_n a_1) \\ = \left( \sum_{k = 1}^{n-1} a_k^2 + a_{k+1}^2 \right) + (a_n^2 + a_1^2) - 2 (a_1 a_2 + a_2 a_3 + \dots + a_{n-1}a_n + a_n a_1) \\ = \left( \sum_{k = 1}^{n-1} a_k^2 + a_{k+1}^2 \right) + (a_n^2 + a_1^2) + \left( \sum_{k = 1}^{n-1} - 2 a_k a_{k+1} \right) - 2a_n a_1 \end{eqnarray}

$$= \sum_{k = 1}^{n-1} (a_k - a_{k+1})^2 + (a_n - a_1)^2 \qquad (*)$$

Now, if $2\left(\sum_{k = 1}^n k^2 - S\right) \ge m$ with equality for some arrangement $\{a_k\}$, then $\sum_{k = 1}^n k^2 - \frac{m}{2} \ge S$; thus, $$\frac{(n)(n+1)(2n+1)}{6} - \frac{m}{2} \qquad(**)$$

would be our maximum value. If we can minimize $(*)$ then, since $m$ will be this minimum, we're done.

What this has boiled down to is trying to show that $(*)$ is a friendly enough expression to minimize. Although it's difficult for me to display in notation, I've come up with a heuristic which suggests that, for a fixed $n$,

$$\min (*) = m = (n-2)(2)^2 + 2(1)^2 = 4n - 6$$

This does, in fact, lead to the correct solution (checking the numerical answer).

Can anyone help me prove that this assertion is correct?

Hint: Prove by induction for $n\geq 3$. Show that adding $n$ into the sequence (in a special place) would increase the sum by at least 4.
Note: The $n=1, 2$ case will have to be dealt with separately, since they give values that don't fit into your sequence.