Let $\sigma, \tau$ be two permutations of the quantity $\{1, 2,. . . , n\}$. Prove that there is a function $f: \{1, 2,. . . , n\} \to \{-1, 1\}$ such that for any $1 \le i \le j \le n$, we have $\left|\sum_{k=i}^{j} f(\sigma (k)) \right| \le 2$ and $\left|\sum_{k=i}^{j} f(\tau (k))\right| \le 2$
Problem
Source: Danube 2009 p5
Tags: combinatorics, permutations, function, Sum, inequalities
GorgonMathDota
31.03.2021 13:38
Bump this.
Rickyminer
31.03.2021 20:31
The key is to make $f(\sigma(2k-1))+f(\sigma(2k))=f(\tau(2k-1))+f(\tau(2k))=0$. If so, when considering consecutive terms, those in the middle cancel out, with at most two possible value left at two ends; therefore, the sum is at most $2$. Now the problem is easy: first we let $f(\sigma(1))=1, f(\sigma(2))=-1$. If $\sigma(2)=\tau(2j-1)$, we let $f(\tau(2j))=1$. Else if $\sigma(2)=\tau(2j)$, we let $f(\tau(2j-1))=1$. This fulfills $f(\tau(2j-1))+f(\tau(2j))=0$. Performing like this, we alternatively "jump" between $\sigma$ and $\tau$. Note that it's always possible to do so as $\tau$ and $\sigma$ are permutations; until once we get back to $\sigma(1)$, forming a loop. Then we start from another unvisited number and do the same thing. If $n$ is even, the above algorithm ends with every number assigned, thus satisfies the problem. If $n$ is odd, the algorithm will be stuck as $\sigma(n)$ and $\tau(n)$ is unpaired. The trick is to add a new number $n+1$ and define $\sigma(n+1)=\tau(n+1)=n+1$, then apply the same method for $n+1$.