Welcome to our community

Be a part of something great, join today!

[SOLVED] Challenge Problem #9 [Olinguito]

Olinguito

Well-known member
Apr 22, 2018
251
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
Apr 22, 2018
251
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
Feb 7, 2012
2,681
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
Feb 7, 2012
2,681
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
Apr 22, 2018
251
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! (Clapping)