IMC 2008 · Problem 6

For a permutation $\sigma = (i_1, i_2, \dots, i_n)$ of $(1, 2, \dots, n)$ define $D(\sigma) = \sum\limits_{k=1}^{n} |i_k - k|$. Let $Q(n,d)$ be the number of permutations $\sigma$ of $(1, 2, \dots, n)$ with $d = D(\sigma)$. Prove that $Q(n,d)$ is even for $d \ge 2n$.