Messed permutations

Question

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?

Answer 1

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})$. To see this, suppose that $\pi\in S_n$ has a messing number of $m$. Consider the discrete $n\times n$ grid, consisting of integer pairs $(x,y)$ with $x,y\in \{1,\dots,n\}$. For each $i\in \{1,\dots,n\}$, define the following subsets of the grid: $$ S_i=\{(x,y)\,:\, |x-i|+|y-\sigma(i)|\le m/2\} $$ Note that the sets $S_i$ contain at least $\Omega(m^2)$ pairs $(x,y)$. This is best seen by drawing out the grid, and these sets. The sets all resemble squares, whose sides are oriented at an angle of $45^\circ$ to the $x$-axis, where the diagonal of the square has length $\approx m/2$. Even if the square clips out of the grid, there are still $\approx (\frac12)(m/2)^2=\frac18m^2$ squares of the $S_i$ which actually lie within the $n\times n$ grid.

The key idea of the proof is that these sets $S_1,\dots,S_n$ are pairwise disjoint. If there existed $i\neq j$ with $S_i\cap S_j$ nonempty, then for any $(x,y)\in S_i\cap S_j$, you would have $$ |i-j|+|\pi(i)-\pi(j)|\le |i-x|+|\pi(i)-y|+|j-x|+|\pi(j)-y|<m/2+m/2=m, $$ but this contradicts the fact that $m=\min\{|i-j|+|\pi(i)-\pi(j)|\,:\, i,j\in n^*,i\neq j\}$.

Since we have $n$ disjoint subsets of a set with cardinality $n^2$, and each subset has cardinality $\Omega(m^2)$, we conclude that $m$ must be $O(\sqrt n)$.

Answer 2

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.