IMO 1977 SL 5

Origin: FRG

Problem

There are 2n words of length n over the alphabet {0, 1}. Prove that the following algorithm generates the sequence w0, w1, . . . , w2n−1 of all these words such that any two consecutive words differ in exactly one digit. (1) w0 = 00 . . .0 (n zeros). (2) Suppose wm−1 = a1a2 . . . an, ai \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 aj in the word wm−1 by 1 −aj. The obtained word is wm.