Problem:
How many sequences of numbers of length eight composed solely of 0s and 1s contain the code 01?
Problem:
How many sequences of numbers of length eight composed solely of 0s and 1s contain the code 01?
Pick one
Solution:
The answer is (D). The number of strings of length 8 formed from the digits 0 and 1 is ; 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 , followed by a block of length of digits 0; as 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 .