sum of absolute differences $|\sigma(i)-i|$ is even

Question

I have to show that for all $\sigma \in S_n$ following equation holds: $\sum_{i=1}^n|\sigma(i)-i|=2k$ for $k\in \mathbb{Z}$.

I have no idea how to show it and would be very grateful for any hint.

Answer 1

HINT: Note that $\sum_{i=1}^n|\sigma(i)-i|$ and $\sum_{i=1}^n(\sigma(i)-i)$ have the same parity, and the latter is easy to calculate.