AMC10 2019 10B, Problem 25

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 $1$s?

Solution: Let $f(n)$ be the number of valid sequences of length $n$ (satisfying the conditions given in the problem). We know our valid sequence must end in a $0$. Then, since we cannot have two consecutive $0$s, it must end in a $10$. Now, we only have two cases: it ends with $010$, or it ends with $110$ which is equivalent to $0110$. Thus, our sequence must be of the forms $0\ldots010$ or $0\ldots0110$. In the first case, the first $n-2$ digits are equivalent to a valid sequence of length $n-2$. In the second, the first $n-3$ digits are equivalent to a valid sequence of length $n-3$. Therefore, it must be the case that $f(n) = f(n-3) + f(n-2)$, with $n \ge 3$ (because otherwise, the sequence would contain only 0s and this is not allowed due to the given conditions). It is easy to find $f(3) = 1$ since the only possible valid sequence is $010$. $f(4)=1$ since the only possible valid sequence is $0110$. $f(5)=1$ since the only possible valid sequence is $01010$. The recursive sequence is then as follows: \[f(3)=1\] \[f(4)=1\] \[f(5) = 1\] \[f(6) = 1 + 1 = 2\] \[f(7) = 1 + 1 = 2\] \[f(8) = 1 + 2 = 3\] \[f(9) = 2 + 2 = 4\] \[f(10) = 2 + 3 = 5\] \[f(11) = 3 + 4 = 7\] \[f(12) = 4 + 5 = 9\] \[f(13) = 5 + 7 = 12\] \[f(14) = 7 + 9 = 16\] \[f(15) = 9 + 12 = 21\] \[f(16) = 12 + 16 = 28\] \[f(17) = 16 + 21 = 37\] \[f(18) = 21 + 28 = 49\] \[f(19) = 28 + 37 = 65\] So, our answer is $\fbox{65}$. Contributors: ~Original Author ~solasky ~BakedPotato66

Answer: 65