Messed permutations Here's an exercise from an old Egyptian textbook published in 1828. I'll try to preserve the main idea while translating it into English.
Let $k\geq2$ be a natural number. Consider a premutation $\sigma\in S_k$ defined on $k^*=\{1,...,k\}$. Define the messing number of $\sigma$ as $m(\sigma)=\min\{|i-j|+|\sigma(i)-\sigma(j)|:i,j\in k^*,i\neq j\}$. Prove that the maximal messing number $\max\{m(\theta):\theta\in S_k\}$ is at most $4$.
I'm pretty sure that there is a mistake but yet didn't find a counterexample. If you manage to find the counterexample (i.e. some permutation with messing number $\geq 5$) or prove that the assertion is true, then please let me know it! Also, if the statement is wrong, what is the lower bound of the maximal messing number?
 A: Suppose $k > 2n^2$ and $\gcd(k,n)=1$
Take $\sigma(i) = in \mod k$.
Then $\sigma(i)-\sigma(j)=(i-j)n \mod k$
If $i \neq j$, then this will be at least $n$. We do have to worry that if $(i-j)n > \frac k2$, then taking the modulus will decrease its absolute value, but if $|i-j| < n$, then we don't have that problem. So at least one of $|i-j|$ and $|\sigma(i)-\sigma(j)|$ will be at least $n$.
Mike Earnest has a tighter bound, but this a simpler proof that arbitrarily large messed numbers are possible.
A: The following permutation of $\{1,\dots,16\}$ has a messing number of $5$:
$$
[4,8,12,16,\;3,7,11,15,\;2,6,10,14,\;1,5,9,13]
$$
This can be generalized to a permutation of $\{1,\dots,n^2\}$ with a messing number of $n+1$.
It can be shown that every permutation of $\{1,\dots,n\}$ has a messing number of at most $O(\sqrt{n})$. The Erdős–Szekeres theorem implies that every such $\pi$ has a monotone subsequence of length $1+\lfloor \sqrt{n-1}\rfloor$. WLOG, this subsequence is increasing. That is, there are indices $i(1)<i(2)<\dots<i(1+\lfloor \sqrt{n-1}\rfloor)$ for which
$$
\pi_{i(1)}<\pi_{i(2)}<\;\;\;\dots\;\;\;<\pi_{i(1+\lfloor \sqrt{n-1}\rfloor)}
$$
If we add up the $\lfloor \sqrt{n-1}\rfloor$ consecutive difference in the above list, the result is $\pi_{i(1+\lfloor \sqrt{n-1}\rfloor)}-\pi_{i(1)}\le n-1$. It follows that the smallest such consecutive difference is at most
$$
\frac{n-1}{\lfloor \sqrt{n-1}\rfloor},
$$
which means that the messing number is at most one more than that. Combined with the family examples at the beginning of my answer, this proves the largest messing number over permutations of $\{1,\dots,n\}$ is to $O(\sqrt{n})$.
