Let $M_n$ be the set of permutations $\sigma\in S_n$ for which there exists $\tau\in S_n$ such that the numbers \[\sigma (1)+\tau(1),\, \sigma(2)+\tau(2),\ldots,\sigma(n)+\tau(n),\]are consecutive. Show that \((M_n\neq \emptyset\Leftrightarrow n\text{ is odd})\) and in this case for each $\sigma_1,\sigma_2\in M_n$ the following equality holds: \[\sum_{k=1}^n k\sigma_1(k)=\sum_{k=1}^n k\sigma_2(k).\] Dan Schwarz
Problem
Source: Romanian TST 1979 Day 1 P3
Tags: algebra, permutations
grupyorum
15.04.2023 21:57
I will prove $M_n\ne\varnothing \Rightarrow 2\mid n+1$. Let $M_n\ne\varnothing$, take any $\sigma\in M_n$. Let $k_i = k+i$ be such that $\sigma(i)+\tau(i)=k_i$ for $1\le i\le n$. Summing these up, and observing $\textstyle \sum_i i = \sum_i\tau(i)=\sum_i\sigma(i)$, we get $k = (n+1)/2$. So, $2\mid n+1$. Now, I prove that $\textstyle\sum_k k\sigma(k)$ is fixed for any $\sigma \in M_n$. To that end, we have $\sigma(i) = k_i-\tau(i)$ and $\textstyle \sum_i \sigma(i)^2 = \sum_i\tau(i)^2 = \sum_i i^2$. So, \[ \sum_i \sigma(i)^2 = \sum_i \bigl(k_i-\tau(i)\bigr)^2 \Rightarrow \sum_i k_i^2 =2\sum_i k_i\tau(i) = 2k\sum_i\tau(i) + 2\sum_i i\tau(i). \]Hence, \[ \sum_i i\tau(i) = \frac12\left(\sum_i \left(\frac{n+1}{2}+i\right)^2 - \frac{n(n+1)^2}{2}\right), \]as claimed. Remark. It remains to prove $M_n\ne\varnothing$ whenever $2\mid n+1$.
Miquel-point
17.04.2023 00:55
If $n$ is odd $M_n$ is nonempty because we can take \[\sigma (i)= \begin{cases} 2i-1 &\text{if } i\le\frac{n+1}2\\ 2i-1-n&\text{if } i>\frac{n+1}2 \end{cases} \text{ and } \tau (i)= \begin{cases} \frac{n+1}2-i+1 &\text{if } i\le\frac{n+1}2\\ \frac{n+1}2-i+1+n&\text{if } i>\frac{n+1}2 \end{cases} \]for each $i=\overline{1,n}$, and we'll obviously have $\sigma(i)+\tau(i)=\frac{n+1}2+i$. For the other parts my solution is basically the same as @above.