Problem:
How many sequences of 0s and 1s of length 19 are there that begin with a 0, end with a 0, contain no two consecutive 0s, and contain no three consecutive 1s?
Answer Choices:
A. 55
B. 60
C. 65
D. 70
E. 75
Solution:
For n≥2, let an be the number of sequences of length n that begin with a 0 , end with a 0, contain no two consecutive 0 s, and contain no three consecutive 1s. In order for the sequence to end with a 0 and satisfy the conditions, it must end either 010 or 0110 . Thus an=an−2+an−3. The initial conditions for this recurrence relation are a2=0,a3=1 (the sequence 010), and a4=1 (the sequence 0110). Then a5=a3+a2=1+0=1,a6=a4+a3=1+1=2, a7=a5+a4=1+1=2, and so on. A bit of calculation produces the display below; a19=65.
nan2031415162728394105117
nan1291312141615211628173718491965
OR
There are four cases, depending on the number of 0 s in the string. If there are 100 s, then there are 91 s, and because no two 0 s can be consecutive, the string must be 0101010101010101010 . If there are 9 0 s and 101 s, then there are 8 gaps between the 0s into which at least one but no more than two 1s must be placed, and there are (28) ways to choose the gaps into which to place two 1s. Similarly, if there are 80 s and 111s, then there are (47) ways to choose the gaps into which to place two 1 s; and if there are 70 s and 121 s, then there are (66) ways to choose the gaps into which to place two 1s. There cannot be more than 10 nor fewer than 7 0s. The number of possible strings is
1+(82)+(74)+(66)=1+28+35+1=(C)65
The problems on this page are the property of the MAA's American Mathematics Competitions