MathDB
Flanders 4 (1991)

Source:

September 7, 2003
algebra solvedalgebra

Problem Statement

A word of length nn that consists only of the digits 00 and 11, is called a bit-string of length nn. (For example, 000000 and 0110101101 are bit-strings of length 3 and 5.) Consider the sequence s(1),s(2),...s(1), s(2), ... of bit-strings of length n>1n > 1 which is obtained as follows : (1) s(1)s(1) is the bit-string 00...0100...01, consisting of n−1n - 1 zeros and a 11 ; (2) s(k+1)s(k+1) is obtained as follows : (a) Remove the digit on the left of s(k)s(k). This gives a bit-string tt of length n−1n - 1. (b) Examine whether the bit-string t1t1 (length nn, adding a 11 after tt) is already in {s(1),s(2),...,s(k)}\{s(1), s(2), ..., s(k)\}. If this is the not case, then s(k+1)=t1s(k+1) = t1. If this is the case then s(k+1)=t0s(k+1) = t0. For example, if n=3n = 3 we get : s(1)=001→s(2)=011→s(3)=111→s(4)=110→s(5)=101s(1) = 001 \rightarrow s(2) = 011 \rightarrow s(3) = 111 \rightarrow s(4) = 110 \rightarrow s(5) = 101 →s(6)=010→s(7)=100→s(8)=000→s(9)=001→...\rightarrow s(6) = 010 \rightarrow s(7) = 100 \rightarrow s(8) = 000 \rightarrow s(9) = 001 \rightarrow ... Suppose N=2nN = 2^n. Prove that the bit-strings s(1),s(2),...,s(N)s(1), s(2), ..., s(N) of length nn are all different.
Back to ProblemsView on AoPS