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.
nan​​20​31​41​51​62​72​83​94​105​117​​
nan​​129​1312​1416​1521​1628​1737​1849​1965​​
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