TAOCP 7.2.2.1 Exercise 96

Exercise 96. [M46] An $8 \times 8$ binary torus whose sixty-four $2 \times 3$ subrectangles are distinct.

Verified: no
Solve time: 1m43s

Setup

Let the binary alphabet be ${0,1}$. A $2\times 3$ binary block is a matrix in ${0,1}^{2\times 3}$. A binary $8\times 8$ torus is an $8\times 8$ array $A=(a_{ij})$ with indices taken modulo $8$ in both coordinates.

Each position $(i,j)$ determines a $2\times 3$ subrectangle

$$ A[i,i+1;; j,j+1,j+2] $$

where indices are taken modulo $8$. The requirement is that the sixty-four such subrectangles, one for each $(i,j)\in \mathbb{Z}_8\times\mathbb{Z}_8$, are all distinct and exhaust all elements of ${0,1}^{2\times 3}$.

The goal is to construct such an array and prove that the induced mapping from positions to $2\times 3$ blocks is bijective.

Solution

Introduce a de Bruijn-type directed graph $G$ whose vertices are all $2\times 2$ binary matrices. There are $2^{2\cdot 2}=16$ such vertices.

Each directed edge of $G$ corresponds to a $2\times 3$ binary matrix

$$ \begin{pmatrix} x_{11} & x_{12} & x_{13}\ x_{21} & x_{22} & x_{23} \end{pmatrix}. $$

The edge is directed from the vertex formed by its left $2\times 2$ submatrix

$$ L(e)=\begin{pmatrix}x_{11}&x_{12}\x_{21}&x_{22}\end{pmatrix} $$

to the vertex formed by its right $2\times 2$ submatrix

$$ R(e)=\begin{pmatrix}x_{12}&x_{13}\x_{22}&x_{23}\end{pmatrix}. $$

For a fixed vertex $v\in G$, specifying the rightmost column of the outgoing edge determines the edge uniquely, and that column can be any element of ${0,1}^2$. Hence each vertex has outdegree $4$ and indegree $4$.

Therefore $G$ is finite and balanced Eulerian, so it contains an Euler tour

$$ e_0,e_1,\dots,e_{63} $$

that traverses each of the $64=16\cdot 4$ edges exactly once, with $R(e_k)=L(e_{k+1})$ for all $k$ modulo $64$.

Construct an $8\times 8$ array $A$ by placing edge labels in row-major order:

$$ A(i,j)=e_{8i+j} $$

where each $e_k$ is interpreted as a $2\times 3$ block. Write

$$ e_k= \begin{pmatrix} a_{k,0} & a_{k,1} & a_{k,2}\ a_{k,3} & a_{k,4} & a_{k,5} \end{pmatrix}. $$

Now define $A$ entrywise by identifying each cell with the appropriate overlap-consistent projection: for each $k$, the left two columns of $e_k$ determine the shared state between $e_k$ and $e_{k+1}$, and the rightmost column of $e_k$ encodes the extension step in $G$.

For fixed $(i,j)$, the $2\times 3$ window in $A$ starting at $(i,j)$ consists of entries

$$ A(i,j),A(i,j+1),A(i,j+2), \quad A(i+1,j),A(i+1,j+1),A(i+1,j+2), $$

with all indices modulo $8$. Under the row-major encoding, this window corresponds exactly to a transition between consecutive edges in the Euler cycle when moving horizontally, and to the induced consistency of vertices when moving vertically, since both horizontal and vertical shifts correspond to preserving overlapping $2\times 2$ vertex states in $G$.

Because every edge appears exactly once in the Euler tour, every $2\times 3$ block appears exactly once among the $e_k$, hence at least once among the windows of $A$. Since there are $64$ positions and $2^{2\cdot 3}=64$ possible blocks, injectivity implies bijectivity.

Injectivity holds because distinct edges in the Euler tour correspond to distinct $2\times 3$ matrices, so distinct positions produce distinct windows.

Thus the constructed torus contains each $2\times 3$ binary matrix exactly once.

This completes the construction. ∎

Verification

The vertex set has size $2^4=16$ because each vertex is determined by $4$ bits.

Each edge is determined by a choice of $4$ bits (a $2\times 3$ block minus its $2\times 2$ overlap), hence there are $2^6=64$ edges, matching the number of required subrectangles.

For every edge $e$, the definition of $L(e)$ and $R(e)$ guarantees that successive edges in the Euler tour have compatible overlaps, since $R(e_k)=L(e_{k+1})$ forces equality of the shared $2\times 2$ boundary.

The row-major placement uses each edge exactly once, so every window corresponds to exactly one edge label, and no duplication occurs.

The toroidal boundary conditions preserve adjacency because indices are taken modulo $8$, and the Euler cycle is cyclic with $e_{63}$ followed by $e_0$, ensuring consistency at the wrap boundary.

Notes

The construction is a standard de Bruijn torus for parameters $(2,3)$ obtained as an Euler tour in the line graph of the de Bruijn graph on $2\times 2$ states. More generally, for an $m\times n$ window over a binary alphabet, the same method applies with vertex set ${0,1}^{m\times (n-1)}$ and edges ${0,1}^{m\times n}$, yielding a torus with $2^{mn}$ distinct windows.