TAOCP 7.2.2.1 Exercise 94
The required object is a binary cycle of length $16$, since the indices in the quadruples are taken modulo $16$.
Section 7.2.2.1: Dancing Links
Exercise 94. [20] [20] (É. Lucas.) Find a binary cycle $(x_0 x_1 \ldots x_5)$ for which the 16 quadruples $x_{k,(k+1)\bmod 16},x_{(k+1)\bmod 16},x_{(k+2)\bmod 16},x_{(k+3)\bmod 16}$ for $0 \le k \le 16$ are distinct.
Verified: yes
Solve time: 1m39s
Solution
The required object is a binary cycle of length $16$, since the indices in the quadruples are taken modulo $16$. We seek a cyclic binary word
$$ x_0x_1\cdots x_{15} $$
such that the $16$ words
$$ x_kx_{(k+1)\bmod 16}x_{(k+2)\bmod 16}x_{(k+3)\bmod 16}, \qquad 0\leq k\leq 15, $$
are all distinct.
Consider the directed graph whose vertices are the binary triples
$$ 000,001,010,011,100,101,110,111. $$
For every binary quadruple $abcd$, insert a directed edge from vertex $abc$ to vertex $bcd$. Each vertex has two outgoing edges, corresponding to appending $0$ or $1$, and two incoming edges, corresponding to deleting the first bit from a quadruple. Hence the graph is balanced and connected, so it has an Euler cycle containing all $16$ edges.
An Euler cycle gives a cyclic sequence of bits by recording the final bit of each traversed edge. For example, choose the Euler cycle whose edge labels are
$$ 0000,0001,0010,0100,1001,0011,0110,1101, $$
$$ 1010,0101,1011,0111,1111,1110,1100,1000. $$
The last bit of each edge label gives the cyclic word
$$ 0000100110101111. $$
The sixteen consecutive quadruples beginning at each position are therefore
$$ \begin{array}{c|c} k & x_kx_{(k+1)\bmod16}x_{(k+2)\bmod16}x_{(k+3)\bmod16}\ \hline 0&0000\ 1&0001\ 2&0010\ 3&0100\ 4&1001\ 5&0011\ 6&0110\ 7&1101\ 8&1010\ 9&0101\ 10&1011\ 11&0111\ 12&1111\ 13&1110\ 14&1100\ 15&1000 \end{array} $$
The displayed list contains all $2^4=16$ binary quadruples exactly once. The construction also proves that no quadruple is omitted: every possible edge of the graph corresponds to one binary quadruple, and the Euler cycle traverses every edge exactly once.
Thus a valid binary cycle is
$$ \boxed{0000100110101111}. $$
This completes the proof. ∎