1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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$

$\endgroup$

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.