# Maximizing the sum of adjacent pairs of elements

I encountered the following interesting problem on stackoverflow:

Given numbers $a(1)<\cdots<a(n)$, find a permutation $\pi$ that maximizes $$\sum_{i=1}^{n-1} a(\pi(i)) a(\pi(i+1)).$$

The answers there claim that the answer doesn't depend on the numbers themselves, and is always given by the order $$\ldots,a(n-5),a(n-3),a(n-1),a(n),a(n-2),a(n-4),\ldots$$ However, the proof (given in the comments) isn't convincing.

Is the answer on stackoverflow correct? Can we prove it?

The following answer is due to Reuven Bar-Yehuda.

Let us call an order maximal if it maximizes the objective function $\sum_{i=1}^{n-1} a(\pi(i)) a(\pi(i+1))$.

Lemma 1. If $\pi$ is maximal then for all $1<i<j<n$, $$\pi(i-1) < \pi(j+1) \text{ iff } \pi(i) < \pi(j).$$

Proof. Suppose that $\pi(i-1) < \pi(j+1)$ and $\pi(i) > \pi(j)$. Form the permutation $\sigma$ by reversing the order all $\pi(i),\ldots,\pi(j)$. Then $$\sum_{k=1}^{n-1} a(\sigma(k)) a(\sigma(k+1)) - \sum_{k=1}^{n-1} a(\pi(k)) a(\pi(k+1)) = \\ a(\sigma(i-1)) a(\sigma(i)) + a(\sigma(j)) a(\sigma(j+1)) - a(\pi(i-1)) a(\pi(i)) - a(\pi(j)) a(\pi(j+1)) = \\ a(\pi(i-1)) a(\pi(j)) + a(\pi(i)) a(\pi(j+1)) - a(\pi(i-1)) a(\pi(i)) - a(\pi(j)) a(\pi(j+1)) = \\ (a(\pi(i-1)) - a(\pi(j+1)) (a(\pi(j)) - a(\pi(i)) > 0. \quad \square$$

Lemma 2. If $\pi$ is maximal then $\pi(1) < \pi(i)$ for all $i \neq n$ and $\pi(n) < \pi(j)$ for all $j \neq 1$.

Proof. Both claims have a similar proof, so we only prove the first. Suppose that $\pi(1) > \pi(i)$ for some $i \neq n$. Form the permutation $\sigma$ by reversing the order of $\pi(1),\ldots,\pi(i)$. Then $$\sum_{k=1}^{n-1} a(\sigma(k)) a(\sigma(k+1)) - \sum_{k=1}^{n-1} a(\pi(k)) a(\pi(k+1)) = \\ a(\sigma(i)) a(\sigma(i+1)) - a(\pi(i)) a(\pi(i+1)) = \\ (a(\pi(1)) - a(\pi(i)) a(\pi(i+1)) > 0. \quad \square$$

Theorem. If $\pi$ is maximal then $\pi$ is the following permutation or its reverse: $$1,3,5,\ldots,6,4,2.$$ Proof. Lemma 2 shows that $a(\pi(1))$ and $a(\pi(n))$ are both smaller than $a(\pi(2)),\ldots,a(\pi(n-1))$, and so $\{\pi(1),\pi(n)\} = \{1,2\}$. Without loss of generality, assume that $\pi(1) = 1$ and $\pi(n) = 2$.

Lemma 1, applied with $i=2$ and $j=3,\ldots,n-1$, shows that $\pi(2)$ is smaller than $\pi(3),\ldots,\pi(n-1)$, and so $\pi(2) = 3$.

Lemma 1, applied with $j=n-1$ and $i=3,\ldots,n-2$, shows that $\pi(n-1)$ is smaller than $\pi(3),\ldots,\pi(n-2)$, and so $\pi(n-1) = 4$.

Continuing in this way, we recover the rest of $\pi$. $\quad \square$