MathDB
algorithm to create a seuqence of 2^n words created by n gifits of {0,1}

Source: 1992 German Federal - Bundeswettbewerb Mathematik - BWM - Round 2 p2

November 20, 2022
algorithmcombinatoricsWords

Problem Statement

All nn-digit words from the alphabet {0,1}\{0, 1\} considered. These 2n2^n words should be in a sequence w0,w1,w2,...,w2−1w_0, w_1, w_2, ..., w_{2^-1} be arranged that wmw_m from wm−1w_{m-1} by changing of a single ornament (m=1,2,3,...,2n−1m = 1, 2, 3, ..., 2n-1). Prove that the following algorithm achievesthis : a) Start with w0=000...00w_0 = 000... 00. b) Let wm−1=a1a2a3...anw_{m-1} = a_1a_2a_3 ... a_n with ai∈{0;1}a_i \in \{0; 1\}, i=1,2,3,...,ni = 1, 2, 3, ..., n. Determine the exponent e(m)e(m) of the highest power of two dividing mm and set j=e(m)+1j = e(m)+1. In wm−1w_{m-1} replace the ornament aja_j with 1−aj1-aj. this is now wmw_m.
Back to ProblemsView on AoPS