4

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?

Kaira
  • 1,451
  • Do you confirm that your sum stops at $n-1$ and not at $n$ , with an $n$th term v=being $\sigma(n)\sigma(1)$ (refering to a cyclic ordering) ? – Jean Marie Apr 16 '20 at 09:28
  • @JeanMarie I had $S(\sigma) = \sigma(1)\sigma(2) + \sigma(3)\sigma(4) + \cdots + \sigma(n-1)\sigma(n)$ in my mind. I think I have wrong definition of $S(\sigma)$.(now edited.) – Kaira Apr 16 '20 at 09:32
  • If so, it is a completely different problem. – Jean Marie Apr 16 '20 at 09:42
  • @JeanMarie Yeah, sorry if you put time into it. – Kaira Apr 16 '20 at 09:58

3 Answers3

3

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)$.

Bart Michels
  • 26,355
3

$$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$

orangeskid
  • 53,909
  • It is interesting to mention that $|\sigma(2k)-\sigma(2k-1)|=1$ can also happen for the reverse permutation $n, n-1, \cdots 2, 1$. – Jean Marie Apr 16 '20 at 13:29
  • @Jean Marie: Yes indeed. And now I see that all these permutations ( $(n/2)! 2^{n/2}$ of them) are the permutations that invariate the partition ${1,2}, {3,4}, \ldots, {n-1,n}$, and form a subgroup. – orangeskid Apr 16 '20 at 23:47
  • 1
    @Jean Marie: I wonder whether the solution to the similar problem with products of threes has a similar solution – orangeskid Apr 17 '20 at 00:02
  • @orangekid I like your "group-theoretic" way to see the issue ; besides, the issue about for example groups of three : I have some doubts about a similar neat result... – Jean Marie Apr 17 '20 at 09:30
  • @Jean Marie: I sketched a proof for grouping (positive) numbers in groups of $m$ ($m\ge 3$, need positive numbers, cannot just add a constant to all)... so I think it is grouping by size – orangeskid Apr 17 '20 at 09:57
2

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$$

Jean Marie
  • 81,803