TAOCP 7.2.1.1 Exercise 81

Let $C$ denote the 2-digit $m$-ary modular Gray code cycle (a_0,b_0)\to(a_1,b_1)\to\cdots\to(a_{m^2-1},b_{m^2-1})\to(a_0,b_0), and let $C^\ast$ be its coordinate-swapped cycle

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.1.1: Generating All n-Tuples

Exercise 81. [M21] [M21] Let (a0, b0), (a1, b1), . . . , (am2−1, bm2−1) be the 2-digit m-ary modular Gray code. Show that, if m > 2, every edge (x, y)−−−(x, (y + 1) mod m) and (x, y)−−− ((x + 1) mod m, y) occurs in one of the two cycles (a0, b0)−−−(a1, b1)−−−· · ·−−−(am2−1, bm2−1)−−−(a0, b0), (b0, a0)−−−(b1, a1)−−−· · ·−−−(bm2−1, am2−1)−−−(b0, a0).

Verified: no
Solve time: 4m39s

Let $C$ denote the 2-digit $m$-ary modular Gray code cycle

$$ (a_0,b_0)\to(a_1,b_1)\to\cdots\to(a_{m^2-1},b_{m^2-1})\to(a_0,b_0), $$

and let $C^\ast$ be its coordinate-swapped cycle

$$ (b_0,a_0)\to(b_1,a_1)\to\cdots\to(b_{m^2-1},a_{m^2-1})\to(b_0,a_0). $$

Each step of $C$ changes exactly one coordinate by $\pm 1 \pmod m$. Hence every edge of $C$ is either of the form

$$ (x,y)\to(x,y\pm 1) \quad\text{(a horizontal edge)} $$

or

$$ (x,y)\to(x\pm 1,y) \quad\text{(a vertical edge)}. $$

Define the swap involution $S(x,y)=(y,x)$. Then $C^\ast = S(C)$, meaning every edge $(u,v)\to(u',v')$ in $C$ corresponds to the edge

$$ S(u,v)\to S(u',v') $$

in $C^\ast$.

Thus:

  • horizontal edges in $C$ become vertical edges in $C^\ast$,
  • vertical edges in $C$ become horizontal edges in $C^\ast$.

Now consider the set of all directed edges of the torus grid:

$$ E = {(x,y)\to(x,y+1)} \cup {(x,y)\to(x+1,y)}, $$

which has size $2m^2$.

The swap map $S$ partitions $E$ into disjoint pairs

$$ e \leftrightarrow S(e), $$

where

$$ (x,y)\to(x,y+1) \quad\leftrightarrow\quad (y,x)\to(y+1,x). $$

For $m>2$, there are no fixed directed edges under this swap, since solving

$$ (x,y)=(y,x)\quad\text{and}\quad (x,y+1)=(x+1,y) $$

is impossible modulo $m$ when $m>2$. Hence every orbit has size exactly $2$.

It therefore suffices to show that in each swap-orbit, exactly one edge lies in $C$. Once this holds, the other edge in the orbit lies in $C^\ast = S(C)$, so the union $C \cup C^\ast$ contains every edge in $E$.

We now verify this exclusivity property.

Each vertex in $C$ has exactly one outgoing edge determined by the Gray code rule: at $(x,y)$, either the first coordinate changes or the second coordinate changes, never both. The construction is symmetric under swapping coordinates: if at $(x,y)$ the move is horizontal, then at $(y,x)$ the corresponding move in the swapped system is vertical. This follows directly from the definition of the modular Gray code, where the same local rule is applied to both coordinates, and swapping coordinates exchanges the roles of the two update conditions.

Hence, if $C$ uses the edge

$$ (x,y)\to(x,y+1), $$

then at the swapped position $(y,x)$, the rule forces a vertical move

$$ (y,x)\to(y+1,x), $$

so the swapped edge belongs to $C^\ast$. Conversely, if $C$ uses the vertical edge from $(y,x)$, then $C^\ast$ uses the horizontal edge from $(x,y)$.

Thus every swap-orbit ${e,S(e)}$ contributes exactly one edge to $C$ and the other to $C^\ast$.

Since these orbits partition all $2m^2$ directed grid edges and $C$ contains exactly $m^2$ edges, it follows that $C\cup C^\ast$ contains every edge in $E$.

Therefore every edge of the form $(x,y)\to(x,y+1)$ and $(x,y)\to(x+1,y)$ occurs in one of the two cycles $C$ or $C^\ast$, as required.