Problem:
How many sequences of zeros and/or ones of length 20 have all the zeros consecutive, or all the ones consecutive, or both?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
By symmetry, half of all such sequences end in zero. Of those, exactly one consists entirely of zeros. Each of the others contains a single subsequence of one or more consecutive ones beginning at position and ending at position with . Thus the number of sequences that meet the requirements is
Let be the set of zero-one sequences of length 20 where all the zeros appear together, and let be the equivalent set of sequences where all the ones appear together. Set contains one sequence with no zeros and 20 sequences with exactly one zero. Each sequence of with more than one zero has a position where the first zero appears and a position where the last zero appears, so there are such sequences, and thus . By symmetry . A sequence in begins with zero and contains from 1 to 20 zeros, or it begins with one and contains from 1 to 20 ones; thus . Therefore the required number of sequences equals
The problems on this page are the property of the MAA's American Mathematics Competitions