TAOCP 7.2.1.1 Exercise 55

Section 7.2.1.1: Generating All n-Tuples

Exercise 55. ▶ [35] [35] (F. Ruskey and C. Savage, 1993.) If (v0, . . . , v2n−1) is an n-bit Gray cycle, the pairs { {v2k, v2k+1} | 0 ≤k < 2n−1 } form a perfect matching between the vertices

314 COMBINATORIAL SEARCHING 7.2.1.1 of even and odd parity in the n-cube. Conversely, does every such perfect matching arise as “half” of some n-bit Gray cycle?

Verified: no
Solve time: 2m36s

Solution

The bit string $(13)$ refers to the binary representation displayed in equation $(13)$ of the section,

$$ a_{23}\dots a_1 a_0 = 011001001000011111101101, $$

which represents an $(s,t)$-combination with $s=11$ zeros and $t=13$ ones. In the grid interpretation of (7.2.1.3), an $(s,t)$-combination corresponds to a path from the southwest corner to the northeast corner of an $s\times t$ grid, consisting of $s$ vertical steps and $t$ horizontal steps.

Under this correspondence, each bit $a_k$ determines a step: $a_k=0$ yields a vertical step, and $a_k=1$ yields a horizontal step. The condition $s+t=24$ ensures that the path has exactly $24$ unit steps.

Decomposing the string into maximal blocks,

$$ 01100;10010;0001;11111;01101, $$

gives a direct description of the path as consecutive runs of vertical and horizontal moves:

the first block contributes $0,1,1,0,0$, the second $1,0,0,1,0$, the third $0,0,0,1$, the fourth $1,1,1,1,1$, and the fifth $0,1,1,0,1$.

Interpreting $0$ as a vertical step $V$ and $1$ as a horizontal step $H$, the path is

$$ VVHHV;HVVHV;VVVH;HHHHH;VHHVH. $$

Equivalently, the path is uniquely determined by starting at $(0,0)$, taking $11$ vertical steps and $13$ horizontal steps in the order prescribed by the above sequence, and ending at $(11,13)$ in the grid. This completes the translation from the bit string $(13)$ to its corresponding lattice path. ∎