The Rotating Drum Problem

Suppose we have a drum that rotates and contains $16$ compartments. Within each compartment we can use either the binary digit $0$ or the binary digit $1$. We want to find an order of binary digits such that all of the $16$-bit sequences of length $4$ appear as consecutive chunks on the rotating drum:

To solve this problem, let's first make a digraph on the eight $3$-bit sequence according to the rule that any binary word abc is also adjacent to $bc0$ and $bc1$. For example, $000$ would be adjacent to $000$ and $001$, or $110$ would be adjacent to $100$ and $101$. We thus get the following digraph:

Imagine the $3$-bit binary words having all of their digits shift to the left where the last digit is replaced by either a $0$ or a $1$ (by our rule above). We thus label the edges with either $0$'s or $1$'s depending on what the last digit changes to. Notice that the first digit "falls off" and the second digit is shifted to the position of the first digit.

Now notice that $\deg ^+ (v) = 2 \quad \mathbf{and} \quad \deg ^- (v) = 2$. Hence this graph must be Eulerian. We will now find an Eulerian trail. For example:

(1)

\begin{align} \quad 000 \rightarrow 000 \rightarrow 001 \rightarrow 010 \rightarrow 100 \rightarrow 001 \rightarrow 011 \rightarrow 110 \rightarrow 101 \rightarrow 010 \rightarrow 101 \rightarrow 011 \rightarrow 111 \rightarrow 111 \rightarrow 110 \rightarrow 100 \rightarrow 000 \end{align}

Now we will write the corresponding values of the arcs to get $0100110101111000$. We thus get the following arrangement:

Binary Word	Decimal Equivalence
$0100$	$4$
$1001$	$9$
$0011$	$3$
$0110$	$6$
$1101$	$13$
$1010$	$10$
$0101$	$5$
$1011$	$11$
$0111$	$7$
$1111$	$15$
$1110$	$14$
$1100$	$12$
$1000$	$8$
$0000$	$0$
$0001$	$1$
$0010$	$2$

Hence we can label our rotating drum in the following manner:

Any $4$ consecutive compartments of the rotating drum will produce one of the unique $4$-bit binary words (note that there are $16$ many $4$-bit binary words equivalent to $0 - 15$).