Problem 732

Solution:

The answer is (D). The number of strings of length 8 formed from the digits 0 and 1 is $2^8$; let us count those that do not contain the code 01. One easily realizes that if such a string contains at least one 0, then all the digits to the right of that 0 are themselves equal to 0: otherwise, in fact, the first 1 that appears after that 0 is necessarily preceded by the digit 0, and we have thus found a substring equal to 01. We therefore obtain that a string that does not contain the code 01 is formed by an initial block of digits 1, say of length $k$, followed by a block of length $8-k$ of digits 0; as $k$ varies between 0 and 8, we obtain the 9 strings of the form described, namely 11111111, 11111110, 11111100, 11111000, 11110000, 11100000, 11000000, 10000000 and 00000000. The answer to the problem is therefore $2^8-9=256-9=247$.