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

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


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


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

Tags:

Permutations

Related

Does the fraction of distinct substrings in prefixes of the Thue–Morse sequence of length $2^n$ tend to $73/96$? Is there a set $A \subset [0,1]$ such that $\int_{A \times A^\text{c}} \frac{\mathrm{d} x \, \mathrm{d} y}{\lvert x - y\vert}=\infty$? Completeness of the category of enriched categories The number of pairs $(m,n)$ of coprime positive integers that divide $k$ is $d(k^2)$, where $d$ is the divisor counting function. Show that $\exists c\in (0,1)$ such that $e^{f'(c)}=f(c)+1.$ How many isosceles triangles do you need to make any polygon? Example of an algebra which is not isomorphic to its opposite Alternative definition of product topology Introductory material for jets and jet bundles Is there a coordinate-free definition of a differential operator? Showing that $\int_{-\infty}^{\infty}\frac{x^2}{(x^2+a^2)(x^2+b^2)}dx=\frac{\pi}{a+b}$ via Fourier Transform Finding the Sum of series $S = \sum_{n=1}^{243} \frac{1}{n^{4/5}} $.

Recent Posts