MathDB

5

Part of 1977 IMO Shortlist

Problems(1)

2^n words - ISL 1987

Source:

9/20/2010
There are 2n2^n words of length nn over the alphabet {0,1}\{0, 1\}. Prove that the following algorithm generates the sequence w0,w1,…,w2n−1w_0, w_1, \ldots, w_{2^n-1} of all these words such that any two consecutive words differ in exactly one digit.
(1) w0=00…0w_0 = 00 \ldots 0 (nn zeros).
(2) Suppose w_{m-1} = a_1a_2 \ldots a_n,  a_i \in \{0, 1\}. Let e(m)e(m) be the exponent of 22 in the representation of nn as a product of primes, and let j=1+e(m)j = 1 + e(m). Replace the digit aja_j in the word wm−1w_{m-1} by 1−aj1 - a_j. The obtained word is wmw_m.
algorithmcombinatoricsCombinatorics of wordsgraph theoryIMO Shortlist