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: 5m27s

$$ \begin{array}{cccccccc} 0&0&0&0&1&0&1&1\ 0&0&0&1&0&0&0&1\ 1&0&0&0&1&0&1&1\ 0&0&1&0&0&0&1&0\ 1&1&0&1&1&1&1&0\ 1&1&1&0&0&1&0&1\ 1&1&0&0&0&1&0&1\ 0&1&1&1&0&1&1&1 \end{array} $$

with the rows and columns interpreted cyclically modulo $8$. We verify that every $2\times3$ subrectangle occurs exactly once.

For a position $(i,j)$, define the associated six-bit word by reading the entries in the order

$$ (i,j),(i,j+1),(i,j+2),(i+1,j),(i+1,j+1),(i+1,j+2). $$

The resulting $8\times8$ array of hexadecimal values, where each value represents the corresponding six-bit word, is

$$ \begin{array}{cccccccc} 00&01&0a&14&28&19&32&24\ 04&08&11&22&05&0b&17&26\ 21&02&0c&10&29&1a&3c&30\ 0e&15&23&07&0f&16&25&03\ 37&2e&1c&39&3a&35&2b&1f\ 3e&34&20&09&12&2d&1b&3f\ 33&27&06&0d&13&2f&1e&3d\ 18&38&31&2a&1d&3b&36&2c \end{array} $$

Each entry in this verification table is a number between $0$ and $63$, representing one of the $2^6=64$ possible $2\times3$ binary rectangles. Reading the table row by row gives

$$ \begin{aligned} &00,01,0a,14,28,19,32,24,\ &04,08,11,22,05,0b,17,26,\ &21,02,0c,10,29,1a,3c,30,\ &0e,15,23,07,0f,16,25,03,\ &37,2e,1c,39,3a,35,2b,1f,\ &3e,34,20,09,12,2d,1b,3f,\ &33,27,06,0d,13,2f,1e,3d,\ &18,38,31,2a,1d,3b,36,2c . \end{aligned} $$

These are precisely the integers

$$ 0,1,2,\ldots,63 $$

in some order. Hence every possible six-bit pattern occurs exactly once among the sixty-four cyclic $2\times3$ subrectangles.

Therefore the displayed $8\times8$ binary torus has sixty-four distinct $2\times3$ subrectangles, as required. $\square$