Problem:
How many sequences of 0 s and 1 s of length 19 are there that begin with a 0 , end with a 0 , contain no two consecutive 0 s, and contain no three consecutive ?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
Let be the number of valid sequences of length (satisfying the conditions given in the problem).
We know our valid sequence must end in a . Then, since we cannot have two consecutive s, it must end in a . Now, we only have two cases: it ends with , or it ends with which is equivalent to . Thus, our sequence must be of the forms or . In the first case, the first digits are equivalent to a valid sequence of length . In the second, the first digits are equivalent to a valid sequence of length . Therefore, it must be the case that , with (because otherwise, the sequence would contain only s and this is not allowed due to the given conditions).
It is easy to find since the only possible valid sequence is since the only possible valid sequence is . since the only possible valid sequence is .
The recursive sequence is then as follows:
So, our answer is .
OR After any particular , the next in the sequence must appear exactly positions down the line. In this case, we start at position and end at position , i.e. we move a total of positions down the line. Therefore, we must add a series of and to get . There are a number of ways to do this:
Case : nine - there is only way to arrange them.
Case : two and six - there are ways to arrange them.
Case : four and three - there are ways to arrange them.
Case : six - there is only way to arrange them.
Summing the four cases gives .
The problems on this page are the property of the MAA's American Mathematics Competitions