MathDB

5

Part of 2009 Danube Mathematical Competition

Problems(1)

sum_{k=i}^{j} f(\sigma (k)) <= 2, for permutations of {1,..,n}

Source: Danube 2009 p5

7/22/2019
Let σ,τ\sigma, \tau be two permutations of the quantity {1,2,...,n}\{1, 2,. . . , n\}. Prove that there is a function f:{1,2,...,n}→{−1,1}f: \{1, 2,. . . , n\} \to \{-1, 1\} such that for any 1≤i≤j≤n1 \le i \le j \le n, we have ∣∑k=ijf(σ(k))∣≤2\left|\sum_{k=i}^{j} f(\sigma (k)) \right| \le 2 and ∣∑k=ijf(τ(k))∣≤2\left|\sum_{k=i}^{j} f(\tau (k))\right| \le 2
combinatoricspermutationsfunctionSuminequalities