Maximum of $S(\sigma) =\sigma(1)\sigma(2)+\sigma(3)\sigma(4) + \cdots +\sigma(n-1)\sigma(n)$ where $\sigma \in S_n$

Question

I want to calculate the maximum for $\displaystyle S(\sigma) = \sigma(1)\sigma(2)+\sigma(3)\sigma(4) + \cdots +\sigma(n-1)\sigma(n)$ where $\sigma \in S_n(n:even)$.

I tried brute force for small $n$.

When $n=2$, any $\sigma \in S_2$ satisfies $S(\sigma )=2$ so the maximum is $2$.

When $n=4$, $S(\sigma) = 14$ is the maximum ($\sigma=1,$unit permutation,if my program didnt have a bug)

When $n=6$, $S(\sigma) =44$ is the maximum. ($\sigma =1$)

So, my guess is that $S(\sigma)$ when $\sigma =1$ will be the maximum, but I don't know how to prove it.

Any ideas?

Answer 1

$$n/2 \le \sum_{k=1}^{n/2} (\sigma(2k)-\sigma(2k-1))^2= \sum_{l=1}^n l^2 - 2S(\sigma)$$ with equality if and only if $|\sigma(2k)-\sigma(2k-1)|=1$ for all $k$.

$\bf{Added:}$ Inspired by this, the following natural problem: given $n = 2k$ (distinct) numbers, how to group them into groups of $2$ so that the sum of products in groups is maximal. The solution is grouping the numbers in order, first $2$, then the next $2$, and so on. To show maximality, it is enough to show that considering the maximizing grouping, the segments $[a_{2i-1}, a_{2i}]$ and $[a_{2j-1}, a_{2j}]$ do not intersect. Now, if they did, we could still increase the sum. We see that we have reduced the argument to the case $k=2$.

As a generalization, how to group $m k$ (positive- this cannot be avoided now) numbers into groups of $m$ such that the sum of the products in the groups is maximal. Again, we have the maximizing solution of grouping in increasing order.

Proof: We reduce to the case $n = 2m$ positive numbers and want to divide them into two groups of size $m$ of such that the sum of the two products is maximum.

Consider the maximum sum $$a_1\ldots a_m + a_{m+1} \ldots a_{2m}$$ Say we have $p=a_1\ldots a_m\le q=a_{m+1} \ldots a_{2m}$. Now, consider indexes $i\in \{1,\ldots,m\}$ and $j\in \{m+1, \ldots, 2m\}$. Since of the maximality (otherwise we could swap $a_i$ and $a_j$) we have

$$(a_i -a_j)(p/a_i - q/a_j)\ge 0$$

that is, $(a_i, a_j)$ and $(p/a_i, q/a_j)$ are ordered in the same way, and so are $(p, q)$. We conclude $a_i \le a_j$

Answer 2

Hint: Yes, $\sigma = 1$ is optimal. You can show this using the rearrangement inequality a few times: https://en.wikipedia.org/wiki/Rearrangement_inequality

---

By the rearrangement inequality, it is no restriction to assume that the optimal $\sigma$ satisfies $$\sigma(1) < \sigma(3) < \sigma(5) <\ldots$$ and $$\sigma(2) < \sigma(4) < \sigma(6) < \ldots \,.$$ We now want to show that $\sigma(2k) < \sigma(2k+1)$ and $\sigma(2k-1) < \sigma(2k+2)$ for $k \geq 1$. This follows from the following:

Fact. If $a < b < c < d$, the biggest value one can get by multiplying them in pairs and adding the products, is $ab+cd$.

Proof. By the rearangement inequality, the biggest ($d$) and the smallest ($a$) cannot be together. So we only have to show that $$ab+cd > ac+bd \,,$$ which is the rearrangement inequality applied to $(a, d)$ and $(b, c)$.

Answer 3

This is not a proof, just a remark.

Your assertion looks exact, but there can be other permutations that reach the same maximum, in particular the reverse permutation $n, n-1, n-2, \cdots 2 , 1$ or others.

If we take the case of $n=6$, the maximum value, which is indeed $44$ can be obtained with these other permutations :

$$\begin{cases}3,4,1,2,6,5&=&(1 \ 3)(2 \ 4)( \ 5 6)\\ 2,1,6,5,3,4&=&(1\ 2)(3 \ 6 \ 4 \ 5)\\4,3,5,6,1,2&=&(1 \ 4 \ 6 \ 2 \ 3 \ 5)\end{cases}$$

etc. (the second column corresponds to the decomposition of the permutation into cycles with disjoint support).

The same phenomenon occurs for $n=8$ and higher values of $n$. For example, for $n=8$, the maximum value 100 can as well be reached by permutation

$$ 5 \ 6 \ 8 \ 7 \ 3 \ 4 \ 2 \ 1$$