Challenge Problem #9 [Olinguito]

[Olinguito]

Let $S_n$ be the group of all permutations of the set $\{1,\ldots,n\}$. Determine whether the following assertions are true or false.

1. For each $\pi\in S_n$,
$$\sum_{i=1}^n\,(\pi(i)-i)\ =\ 0.$$

2. If
$$\sigma_\pi\ =\ \sum_{i=1}^n\,\left|\pi(i)-i\right|$$
for each $\pi\in S_n$, then $\sigma_\pi$ is an even number.

Bonus challenge: Find $\displaystyle\max_{\pi\in S_n}\,\sigma_\pi$.

 

[Olinguito]

I have solved the first part of the problem.

Spoiler

$$\sum_{i=1}^n\,(\pi(i)-i))\ =\ 0$$
follows from the fact that
$$\sum_{i=1}^n\,\pi(i)\ =\ \sum_{i=1}^n\,i$$
(the terms of the LHS sum are precisely those of the RHS sum in a different order).

 

[Opalg]

[sp]For the second part, notice that by the first part, the sum of the negative terms in $\sum(\pi(i) - i)$ is the negative of the sum of the positive terms. So when you replace the negative terms by their absolute values, the resulting sum is twice the sum of the positive terms. In other words, it must be an even number.
[/sp]

 

[Opalg]

Bonus challenge: Find $\displaystyle\max_{\pi\in S_n}\,\sigma_\pi$.

[sp]That part looks harder. After experimenting with small values of $n$, I believe that \(\displaystyle \max_{\pi\in S_n}\sigma_\pi = \bigl\lfloor\tfrac{n^2}2\bigr\rfloor\). But I don't have a proof of that.
[/sp]

 

[Olinguito]

[sp]That part looks harder. After experimenting with small values of $n$, I believe that \(\displaystyle \max_{\pi\in S_n}\sigma_\pi = \bigl\lfloor\tfrac{n^2}2\bigr\rfloor\). But I don't have a proof of that.
[/sp]

Spoiler

It would be $\dfrac{n^2}2$ if $n$ is even and $\dfrac{n^2-1}2$ if $n$ is odd – a simple induction clinches the proof.

Thanks for helping me with the challenge! (Clapping)