MathDB

3

Part of 1991 Czech And Slovak Olympiad IIIA

Problems(1)

permutations inequality

Source: Czech And Slovak Mathematical Olympiad, Round III, Category A 1991 p3

2/11/2020
For any permutation pp of the set {1,2,...,n}\{1,2,...,n\}, let us denote d(p)=∣p(1)−1∣+∣p(2)−2∣+...+∣p(n)−n∣d(p) = |p(1)-1|+|p(2)-2|+...+|p(n)-n|. Let i(p)i(p) be the number of inversions of pp, i.e. the number of pairs 1≤i<j≤n1 \le i < j \le n with p(i)>p(j)p(i) > p(j). Prove that d(p)≤2i(p)d(p)\le 2i(p)$.
inequalitiespermutationalgebra