Vtyjkyuk

Originating from a table permutation problem (which I first thought was easy...) is my following question, about some permutations of cyclic groups:

Let $nge 1$ be an integer and identify the cyclic group $mathbbZ/nmathbbZ$ with the set $0,1,...,n-1$ through the "obvious" bijection $phi$, whose inverse is just given by

$$0,1,...,n-1ni ilongmapsto bariinmathbbZ/nmathbbZ$$

Now define a distance in $mathbbZ/nmathbbZ$ by setting
$$d(x,y)=min(phi(x-y),phi(y-x))in0,1,...,n-1,$$
for all $(x,y)in(mathbbZ/nmathbbZ)^2$.

In more concrete terms, just put clockwise the elements of $mathbbZ/nmathbbZ$ on the vertices of a regular $n$-gone (or sit $n$ guests around a circular table). The distance between two elements of $mathbbZ/nmathbbZ$ is just the usual graph distance between the associated vertices.

My question is:

Assume $sigma$ is a disturbing permutation of $mathbbZ/nmathbbZ$, i.e., a permutation such that:

• $sigma(0)=0$,


• For all $(x,y)in (mathbbZ/nmathbbZ)^2$, $d(sigma(x),sigma(y))neq d(x,y)$,

(in the table analogy, $sigma$ is just a permutation of the guests such that the distance between any two guests before and after the permutation is different)

Then is it true that $sigma$ is (i.e. has to be) a group automorphism of $mathbbZ/nmathbbZ$?

Here is an answer I found somewhere (reformulated a little bit) to a weaker problem, which was my original one:

"An even number of guests are sitting around a circular table. They all stand up and sit again, but in a different order. Show that there are at least two people which are sitting at the same distance (=minimal number of guests between them) as before"

My claim about any "disturbing permutation" being a group automorphism is not proved and is perhaps (trivially) wrong.

Set $n=2m$ and let $f:mathbbZ/nmathbbZrightarrow mathbbZ/nmathbbZ$ be a permutation. There are two cases:

1- For all $din mathbbZ/nmathbbZ$, $f_d:=f+d$ has a fixed point, i.e. for all $d$ one has some $i_dinmathbbZ/nmathbbZ$ such that $f(i_d)+d=i_d$.
Thus one has
$$sum_dinmathbbZ/nmathbbZi_d=sum_dinmathbbZ/nmathbbZ(f(i_d)+d)
=sum_dinmathbbZ/nmathbbZf(i_d)+sum_dinmathbbZ/nmathbbZd$$
But the $i_d$'s have to be pairwise distinct by construction, so $dmapsto i_d$ and $dmapsto f(i_d)$ are bijections of $mathbbZ/nmathbbZ$, therefore $sum_dinmathbbZ/nmathbbZd$ has to be $0$ in $mathbbZ/nmathbbZ$.
But $sum_dinmathbbZ/nmathbbZd=fracn(n-1)2=m(2m-1)equiv -mneq 0$ $mod n$, which gives a contradiction.

2- There is some $dinmathbbZ/nmathbbZ$ such that $f_d$ has no fixed point. The problem is translation-invariant (as we are only dealing with distances) so we may still assume $d=0$ (up to replacing $f$ by $f_d$), i.e. $f$ has no fixed point.
Let $f':=f-id$. As $f'(i)neq 0$, $forall iinmathbbZ/nmathbbZ$ then $f$ is not surjective, thus not injective i.e., there exists $ineq j$ such that $f'(i)=f'(j)$, i.e.,
$f(i)-f(j)=-(i-j)$ which means $d(f(i),f(j))=d(i,j)$.