# 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?

• I could not find any counterexamples when $1 \le k \le 9$ (brute force), so unless there is a large counterexample, the statement might be true. Aug 21, 2021 at 17:06
• @Phicar For that argument I'm getting $2 \cdot \frac{(k-1)k(k+1)}{6} > 4 \frac{k(k-1)}{2} \implies k > 5$. I'm guessing you got $k > 11$ from $2 \cdot \frac{(k-1)k(k+1)}{6} > 4 k(k-1)$ but I'm not sure that is correct. Aug 21, 2021 at 17:41
• @angryavian Oh, yes. I did forget a $2$. nevermind then. Thanks for seeing that. Aug 21, 2021 at 17:46

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| 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)$$.

• @HolyMoly Ah, thank you, fixed. I'm glad you shared this cool problem! Aug 22, 2021 at 4:26

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.

• @DavidZ You're responding to a comment that was posted before I make an edit addressing that comment. Aug 22, 2021 at 18:39