Question 53
Given a string of digits 0 and 1, Giacomo would like to divide it into blocks of 2 or 3 consecutive digits so as to satisfy one of the following two conditions:
(1) in every block, every 0 digit (if any) appears to the left of every 1 digit (if any). That is, the allowed blocks are $00,01,11,000,001,011,111$;
(2) in every block, every 0 digit (if any) appears to the right of every 1 digit (if any). That is, the allowed blocks are $00,10,11,000,100,110,111$.
For example, for the string 011011 the division $01|10|11$ is not acceptable, because the blocks are neither all of type (1) nor all of type (2). The division 011|011, on the other hand, is acceptable, because all the blocks are of type (1).
a. Let $m, n$ be integers greater than or equal to 0, with $m+n \geq 2$. Prove that the string consisting of $m$ digits 0 followed by $n$ digits 1 can be divided into blocks as Giacomo wishes.
b. Let $l \geq 4$ be an integer. Prove that the number of strings of digits 0 and 1 of length $l$ for which Giacomo cannot make a division as above is $2^{l-3}$.
(1) in every block, every 0 digit (if any) appears to the left of every 1 digit (if any). That is, the allowed blocks are $00,01,11,000,001,011,111$;
(2) in every block, every 0 digit (if any) appears to the right of every 1 digit (if any). That is, the allowed blocks are $00,10,11,000,100,110,111$.
For example, for the string 011011 the division $01|10|11$ is not acceptable, because the blocks are neither all of type (1) nor all of type (2). The division 011|011, on the other hand, is acceptable, because all the blocks are of type (1).
a. Let $m, n$ be integers greater than or equal to 0, with $m+n \geq 2$. Prove that the string consisting of $m$ digits 0 followed by $n$ digits 1 can be divided into blocks as Giacomo wishes.
b. Let $l \geq 4$ be an integer. Prove that the number of strings of digits 0 and 1 of length $l$ for which Giacomo cannot make a division as above is $2^{l-3}$.