“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.

This solution follows naturally from considering the equality case.

Note: The $n=1, 2$ case will have to be dealt with separately, since they give values that don't fit into your sequence.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.