Originating from a table permutation problem (which I first thought was easy...) is my following question, about some permutations of cyclic groups:
Let $n\ge 1$ be an integer and identify the cyclic group $\mathbb{Z}/n\mathbb{Z}$ with the set $\{0,1,...,n-1\}$ through the "obvious" bijection $\phi$, whose inverse is just given by
$$\{0,1,...,n-1\}\ni i\longmapsto \bar{i}\in\mathbb{Z}/n\mathbb{Z}$$
Now define a distance in $\mathbb{Z}/n\mathbb{Z}$ by setting $$d(x,y)=\min(\phi(x-y),\phi(y-x))\in\{0,1,...,n-1\},$$ for all $(x,y)\in(\mathbb{Z}/n\mathbb{Z})^2$.
In more concrete terms, just put clockwise the elements of $\mathbb{Z}/n\mathbb{Z}$ on the vertices of a regular $n$-gone (or sit $n$ guests around a circular table). The distance between two elements of $\mathbb{Z}/n\mathbb{Z}$ is just the usual graph distance between the associated vertices.
My question is:
Assume $\sigma$ is a disturbing permutation of $\mathbb{Z}/n\mathbb{Z}$, i.e., a permutation such that:
- $\sigma(0)=0$,
- For all $(x,y)\in (\mathbb{Z}/n\mathbb{Z})^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 $\mathbb{Z}/n\mathbb{Z}$?
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:\mathbb{Z}/n\mathbb{Z}\rightarrow \mathbb{Z}/n\mathbb{Z}$ be a permutation. There are two cases:
1- For all $d\in \mathbb{Z}/n\mathbb{Z}$, $f_d:=f+d$ has a fixed point, i.e. for all $d$ one has some $i_d\in\mathbb{Z}/n\mathbb{Z}$ such that $f(i_d)+d=i_d$. Thus one has $$\sum_{d\in\mathbb{Z}/n\mathbb{Z}}i_d=\sum_{d\in\mathbb{Z}/n\mathbb{Z}}(f(i_d)+d) =\sum_{d\in\mathbb{Z}/n\mathbb{Z}}f(i_d)+\sum_{d\in\mathbb{Z}/n\mathbb{Z}}d$$ But the $i_d$'s have to be pairwise distinct by construction, so $d\mapsto i_d$ and $d\mapsto f(i_d)$ are bijections of $\mathbb{Z}/n\mathbb{Z}$, therefore $\sum_{d\in\mathbb{Z}/n\mathbb{Z}}d$ has to be $0$ in $\mathbb{Z}/n\mathbb{Z}$. But $\sum_{d\in\mathbb{Z}/n\mathbb{Z}}d=\frac{n(n-1)}{2}=m(2m-1)\equiv -m\neq 0$ $\mod n$, which gives a contradiction.
2- There is some $d\in\mathbb{Z}/n\mathbb{Z}$ 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 i\in\mathbb{Z}/n\mathbb{Z}$ then $f$ is not surjective, thus not injective i.e., there exists $i\neq 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)$.