Q5 Matemática  (IMO Shortlist 1977)

Existem $2^n$ palavras de comprimento $n$ sobre o alfabeto $\{0,1\}$. Prove que o algoritmo a seguir gera a sequência $w_0,w_1,\dots ,w_{2^n-1}$ de todas essas palavras de modo que quaisquer duas palavras consecutivas diferem em exatamente um dígito. (1) $w_0=00\dots 0$ ($n$ zeros). (2) Suponha $w_{m-1}=a_1{a}_2\dots a_n,a_i\in \{0,1\}$. Seja $e(m)$ o expoente de $2$ na representação de $n$ como produto de primos, e seja $j=1+e(m)$. Substitua o dígito $a_j$ na palavra $w_{m-1}$ por $1-a_j$. A palavra obtida é $w_m$.