MathDB
permutations inequality

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

February 11, 2020
inequalitiespermutationalgebra

Problem Statement

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)$.
Back to ProblemsView on AoPS