Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Are the 15 positions on the circle necessarily uniformly spaced? –  Henning Makholm Jan 18 '13 at 1:13
2  
@joriki: I haven't tried very hard to understand your code, but what is wrong with 5 objects and (0 2 4 1 3)? (Or in general any prime number $p\ge 5$ of objects and doubling positions modulo $p$, or even more generally $q$ objects and multiplying positions by $k$ modulo $q$ where $\{k-1,k,k+1\}$ are each coprime with $q$ (which requires that $q$ is not a multiple of $3$))? –  Henning Makholm Jan 18 '13 at 1:23
    
My own computer search confirms that there is no solution for $n=15$, and quickly finds a number of solutions for $n=11$, including 1 3 5 7 9 11 2 4 6 8 10, and many solutions for $n=13$, such as 1 3 10 6 11 5 12 4 13 7 9 2 8. I will make the code available if anyone cares. –  MJD Jan 18 '13 at 1:35
    
You're right, there was a bug in my code. I've fixed it, and am now getting the same results as @MJD. I'll delete my first comment since it might mislead if people don't read further. –  joriki Jan 18 '13 at 1:42
1  
@AlexanderGruber gist.github.com/4561589 ; please feel free to email me if you want to discuss anything. –  MJD Jan 18 '13 at 2:07

2 Answers 2

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.

share|improve this answer
    
Very nice, problem solved. –  joriki Jan 18 '13 at 2:00
    
Under other circumstances I might have made this a CW post, since I didn't solve the problem myself, but in this case the research effort was significant, and I feel that I have added some value. –  MJD Jan 18 '13 at 2:01
    
@joriki Don't you have an OEIS account? If so, you might let them know that their hyperlink to the Hsiang paper is no good, and that they should replace it with the CiteSeer link I provided. –  MJD Jan 18 '13 at 2:04
2  
"and I feel that I have added some value" -- You did. It would have been very difficult to find this connection without writing the code to determine the numbers up to $A(13)=348$. By the way the related OEIS entry A007705 gives a reference from $1921$ and says that Polya proved the result that $TQ(n)\ne0$ if and only if $n$ is coprime to $6$. –  joriki Jan 18 '13 at 2:05

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$-queens problem, in Discrete Mathematics 19 (1977), 289-91. 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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.