TAOCP 7.2.2.1 Exercise 94
We construct a binary cycle $(x_0 x_1 \ldots x_{15})$ by setting (x_0 x_1 \ldots x_{15}) = 0000100110101111.
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: 1m06s
Solution
We construct a binary cycle $(x_0 x_1 \ldots x_{15})$ by setting
$$ (x_0 x_1 \ldots x_{15}) = 0000100110101111. $$
Thus
$$ (x_0,\ldots,x_{15}) = (0,0,0,0,1,0,0,1,1,0,1,0,1,1,1,1). $$
For each $k$ with $0 \le k \le 15$, define the quadruple
$$ Q_k = x_k x_{k+1} x_{k+2} x_{k+3}, $$
where subscripts are taken modulo $16$.
The list of quadruples is obtained directly by reading the cycle cyclically:
$$ \begin{aligned} Q_0 &= 0000, & Q_1 &= 0001, & Q_2 &= 0010, & Q_3 &= 0100, \ Q_4 &= 1001, & Q_5 &= 0011, & Q_6 &= 0110, & Q_7 &= 1101, \ Q_8 &= 1010, & Q_9 &= 0101, & Q_{10} &= 1011, & Q_{11} &= 0111, \ Q_{12} &= 1111, & Q_{13} &= 1110, & Q_{14} &= 1100, & Q_{15} &= 1000. \end{aligned} $$
Each element of this list is a binary string of length $4$. The list contains $16$ elements. The set of all binary strings of length $4$ also has size $2^4 = 16$.
Direct inspection shows that each of the $16$ possible quadruples appears exactly once among $Q_0, Q_1, \ldots, Q_{15}$. Therefore the mapping $k \mapsto Q_k$ is a bijection from ${0,1,\ldots,15}$ to the set of all binary $4$-tuples.
Hence the cyclic sequence $(x_0 x_1 \ldots x_{15})$ has the property that the $16$ quadruples $x_k x_{k+1} x_{k+2} x_{k+3}$ for $0 \le k \le 15$ are distinct.
This completes the proof. ∎