Open

Posted online: 2018-10-12 20:00:48Z by Marcel L.J. Van de Vel595

Cite as: P-181012.1

**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.

No solutions added yet

Created at: 2018-10-12 20:00:48Z

No remarks yet