Maximum of $S(\sigma) =\sigma(1)\sigma(2)+\sigma(3)\sigma(4) + \cdots +\sigma(n-1)\sigma(n)$ where $\sigma \in S_n$ 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?
 A: 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)$.
A: $$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$ 
A: 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$$
