# [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! 