MathDB

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 \ldots 0

(

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}

1 - a_j

. The obtained word is

w_m

Problem Statement