Permuting elements of a set around a circle

Given $15$ objects placed around a circle, is it possible to permute their order such that the distance between any two elements is different in the second permutation from that in the original state?

Solution 1:

OEIS notes that this is closely related to the problem of whether there is a solution to the toroidal $N$ queens problem, which is the problem of arranging $N$ chess queens on an $N\times N$ chessboard so that none attacks another, where the opposite pairs of edges of the board are identified. It refers to The Cyclic Complete Mappings Counting Problems, Hsiang, Shieh, and Chen, 2002. Theorem 2 on page 6 of that paper states: $$TQ(n) = 0 \text{ if and only if } 2 | n \text{ or } 3 | n.$$

$TQ(n)$ is the number of solutions to the toroidal $N$-queens problem, and is easily seen to be equal to $n\cdot A(n)$, where $A(n)$ is the number of solutions to the circle arranging problem we are solving. In particular, $TQ(15) = 0$, so $A(15) = 0$.

Unfortunately, the paper does not provide a proof. However, as Joriki notes in the comments, the theorem is due to Pólya, probably in Über die 'doppelt-periodischen' Lösungen des $n$-Damen-Problems, Mathematische Unterhaltungen und Spiele., (1918), pp. 364–374; according to Wikipedia, this appears in George Pólya: Collected papers Vol. IV, G-C. Rota, ed., MIT Press, Cambridge, London, 1984, pp. 237–247. Web search for "toroidal $n$-queens" may produce something more immediately useful.

Mathworld cites Vardi, I. "The $n$-Queens Problems." Ch. 6 in Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 107–125, 1991.

Solution 2:

This sci.math post says that the literature contains several independent proofs of the result that the toroidal $n$-queens problem has a solution iff $\gcd(n,6)=1$ and gives six references. I have access to one of them, Torleiv Kløve, The modular $n$-queen problem, in Discrete Mathematics 19 (1977), 289--291. The proof there is short enough to be worth typing out here.

We want a function $f:\Bbb Z/n\Bbb Z\to\Bbb Z/n\Bbb Z$ such that $f$, $f+\mathrm{id}_{\Bbb Z/n\Bbb Z}$, and $f-\mathrm{id}_{\Bbb Z/n\Bbb Z}$ are all injections. The theorem is that such an $f$ exists iff $\gcd(n,6)=1$.

Proof. Suppose that $f$ is such a function, and let

$$S=\sum_{k\in\Bbb Z/n\Bbb Z}k^2\quad\text{and}\quad T=\sum_{k\in\Bbb Z/n\Bbb Z}kf(k)\;.$$

Then $\displaystyle\sum_{k\in\Bbb Z/n\Bbb Z}f(k)^2=S$, since $f$ is injective. Since $f+\mathrm{id}_{\Bbb Z/n\Bbb Z}$ and $f-\mathrm{id}_{\Bbb Z/n\Bbb Z}$ are also injective,

$$S=\sum_{k\in\Bbb Z/n\Bbb Z}\big(f(k)\pm k\big)^2=\sum_{k\in\Bbb Z/n\Bbb Z}f(k)^2\pm 2\sum_{k\in\Bbb Z/n\Bbb Z}kf(k)+\sum_{k\in\Bbb Z/n\Bbb Z}k^2=2S\pm 2T\;,$$

$2S=4S$, and $2S=0$ in $\Bbb Z/n\Bbb Z$. In $\Bbb Z$, therefore, we have

$$2\sum_{k=0}^{n-1}k^2=\frac{n(n-1)(2n-1)}3\equiv 0\pmod n$$

and hence $\gcd(n,3)=1$.

He now appeals to N.J. Fine’s solution of problem E 1699 (Amer. Math. Monthly 72 (1965), 552-3). Specialized to the present setting, the argument (which may have given Kløve the idea for his proof) is that

$$\sum_{k\in\Bbb Z/n\Bbb Z}\big(f(k)+k\big)=2\sum_{k\in\Bbb Z/n\Bbb Z}k$$

in $\Bbb Z/n\Bbb Z$, but if $n$ is even, then $$\sum_{k=0}^{n-1}k=\frac{n(n-1)}2\equiv-\frac{n}2\equiv\frac{n}2\pmod n\;,$$

so in $\Bbb Z/n\Bbb Z$ we have $$\sum_{k\in\Bbb Z/n\Bbb Z}\big(f(k)+k\big)=2\cdot\frac{n}2=0\ne\sum_{k\in\Bbb Z/n\Bbb Z}k\;,$$ and $f+\mathrm{id}_{\Bbb Z/n\Bbb Z}$ cannot be injective. Thus, $n$ must be odd, and $\gcd(n,6)=1$.

Conversely, if $\gcd(n,6)=1$, then $f(k)=2k$ is a solution. $\dashv$