[SOLVED]Challenge Problem #9 [Olinguito]

Olinguito

Well-known member
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

Well-known member
I have solved the first part of the problem.

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

MHB Oldtimer
Staff member
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.

Opalg

MHB Oldtimer
Staff member
Bonus challenge: Find $\displaystyle\max_{\pi\in S_n}\,\sigma_\pi$.
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.

Olinguito

Well-known member
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.
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!