8
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – angryavian
    Commented Aug 21, 2021 at 17:06
  • 1
    $\begingroup$ @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. $\endgroup$
    – angryavian
    Commented Aug 21, 2021 at 17:41
  • $\begingroup$ @angryavian Oh, yes. I did forget a $2$. nevermind then. Thanks for seeing that. $\endgroup$
    – Phicar
    Commented Aug 21, 2021 at 17:46

2 Answers 2

13
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ @HolyMoly Ah, thank you, fixed. I'm glad you shared this cool problem! $\endgroup$ Commented Aug 22, 2021 at 4:26
  • $\begingroup$ In the definition of $S_i$, you'll probably need $|x - i| + |y - \sigma(i)| < m/2$ with strict inequality. $\endgroup$ Commented May 30 at 18:28
5
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .