Rotating pairs into disjoint positions on a regular $n$-gon

Problem's Description

Pairs problem: Given $t \geq 2$ pairs of vertices of a regular $n$-gon ($n \geq 3$ integer) with $2t \leq n$, is it possible to rotate the individual pairs to mutually disjoint copies? What is the largest number $t = t(n)$ of pairs that always rotate apart, regardless of the data? For instance, if $n \geq 8$ is a multiple of $4$ and $t = \frac{n}{4} + 1$ then $t$ pairs can be rotated apart. For $5 \leq n \leq 38$ computations show that the following proposal works: $t =\frac{n}{3}$ if $n$ is divisible by $3$ and $t =\lceil \frac{n+2}{3} \rceil$ otherwise. For $n \leq 11$, or if $n$ is a multiple of $3$, or if $n = 14, 20$, this boundary is the desired $t(n)$. The value is not the best possible for other $n \leq 32$. A peculiar result is that $n$ is of type $8x$ or $8x + 2$ if and only if the $n$-gon can be partitioned into $\frac{n}{2}$ pairs with all different diameters $1,2,\ldots,\frac{n}{2}$. Difficulties in determining the exact value of $t(n)$ are seemingly due to the appearance of pairs having the same diameter.

The pairs problem looks like a mathematical description of a children's game (it could be played on a circular board with pairs of clock pointers that can be fixed with certain diameters (angles) and rotated rigidly around the clock, though I am not aware of any implementations). However the question belongs to a chain of complex problems with many unknown answers.

First, it can be generalized to the Rotation problem: Consider $t \geq 2$ subsets $S_1,..,S_t$ of the $n$-gon's vertices. The sum $s$ of the sizes must be $\leq n$. Is it possible to find rotations $r_i , i = 1 .. t$ of the $n$-gon such that $r_i(S_i) \cap r_j(S_j) = \emptyset$ for all $i \neq j$ in $1 .. t$? The answer is known to be affirmative provided $\frac{t-1}{t^2} s^2 < n$. (There is also a minor technical condition if $t \geq3$ and $n > 80$.) This result appears to be useful but little is known about its sharpness. Cyclotomic polynomials can be used to prove that any $t$ sets of size $m$ can be rotated apart in a regular $n$-gon provided $n = (t-1) m^2$. For $m = 2$ this agrees with a result on pairs quoted above. Almost nothing is known about the sharpness. For instance, three sets of size $5$ can always be rotated apart in a regular $50$-gon (case $m = 5, t = 3$). Is this still true in a regular $49$-gon? (We could have used almost any $m, t$ and the corresponding $n$ here.)

The rotation problem is in turn connected with a problem on shuffling a (formal) $n$-square $\{0,1, \ldots, n-1 \}^2$. Each member of the square is seen as a cell and is represented by a pair $(k,r)$ where $0 \leq k, r < n$ represent a column number, resp., a row number. A horizontal move (H-move) of the square consists in rotating some rows cyclically by some integer amount. Different rows may be given a different rotation amount. Similarly, a vertical move (V-move) rotates some columns cyclically by some integer amount. Any composed move can be reduced to an alternating composition of H-moves and V-moves. A shuffle consists of a V-move followed by an H-move. We can now formulate the Shuffle problem: can each set of $n$ cells in a formal $n$-square be mapped onto a column transversal (i.e., a set meeting each column once) with one shuffle? Note that the final H-move triggers the rotation problem. (The preliminary V-move does a kind of optimization to achieve conditions required for solving a rotation problem.) The shuffle problem has been solved affirmatively for $n \leq 34$ and for $n = 37$. The problem is open for all other $n$.

On top of the problem chain we have equi-$n$-squares. Consider a formal $n$-square where each cell is assigned one of the digits $0, 1, \ldots, n-1$ such that each digit (often called a color) occurs $n$ times. The digit assignment is considered a state of the formal square. The entire structure is called an *equi-$n$-square*. For each $n$ with a positive answer to the shuffle problem, a generic method originates that draws theoretically unpredictable numbers of size $< n^n$ from a shuffled equi-$n$-square. (A realistic version with shuffles driven by some pseudo-random number generator is currently being studied.) For a different spin-off an equi-$n$-square can be materialized as a colored torus, leading to problems as with Rubik's cube: how many shuffles are needed to "restore" some original state? Contrary to Rubik's cube, any state can be restored. Quantitive answers exist based on solutions of the shuffle problem, but once again little is known on the sharpness of the answers.

1. ArticleIs an originShuffled equi-$n$-squares

   • M. Van de Vel

   submitted to Journal of Combinatorial Mathematics and Combinatorial ComputingarXivfulltext