MathDB
IMC 2008 Day 1 P6 - Permutation Distances

Source: Problem 6

July 30, 2008
IMCcollege contests

Problem Statement

For a permutation σ∈Sn \sigma\in S_n with (1,2,…,n)↦(i1,i2,…,in) (1,2,\dots,n)\mapsto(i_1,i_2,\dots,i_n), define D(\sigma) \equal{} \sum_{k \equal{} 1}^n |i_k \minus{} k| Let Q(n,d) \equal{} \left|\left\{\sigma\in S_n : D(\sigma) \equal{} d\right\}\right| Show that when d≥2n d \geq 2n, Q(n,d) Q(n,d) is an even number.
Back to ProblemsView on AoPS