Question 5
(FRG 5) There are $2^n$ words of length $n$ over the alphabet $\{0,1\}$. Prove that the following algorithm generates the sequence $w_0,w_1,\ldots,w_{2^n-1}$ of all these words such that any two consecutive words differ in exactly one digit.
(1) $w_0=00\ldots0$ ($n$ zeros).
(2) Suppose $w_{m-1}=a_1a_2\ldots a_n$, $a_i\in\{0,1\}$. Let $e(m)$ be the exponent of $2$ in the representation of $n$ as a product of primes, and let $j=1+e(m)$. Replace the digit $a_j$ in the word $w_{m-1}$ by $1-a_j$. The obtained word is $w_m$.
(1) $w_0=00\ldots0$ ($n$ zeros).
(2) Suppose $w_{m-1}=a_1a_2\ldots a_n$, $a_i\in\{0,1\}$. Let $e(m)$ be the exponent of $2$ in the representation of $n$ as a product of primes, and let $j=1+e(m)$. Replace the digit $a_j$ in the word $w_{m-1}$ by $1-a_j$. The obtained word is $w_m$.