Maths Olympiad Prep

Library / /2 of 9

Combinatorics Difficulty 4.0 AMC 10/12 Find the answer Italy

Problem:

How many sequences of numbers of length eight composed solely of 0s and 1s contain the code 01?

Pick one

Solution

Solution:

The answer is (D). The number of strings of length 8 formed from the digits 0 and 1 is 282^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 kk, followed by a block of length 8k8-k of digits 0; as kk 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 289=2569=2472^8-9=256-9=247.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.