2019 AMC 10B Problem 25

Between consecutive $0$s there must be at least one $1$ (no $00$) and at most two (no $111$). So after the initial $0$, the string is a sequence of blocks, each either $10$ or $110$.

Suppose there are $k$ blocks, $j$ of which are $110$. The length is
$$1 + 2k + j = 19 \quad\Longrightarrow\quad j = 18 - 2k.$$
Since $0 \le j \le k$, we need $6 \le k \le 9$. For each $k$, choose which $j$ of the $k$ blocks are the long ones:

Total: $1 + 35 + 28 + 1 = 65$.

The answer is $\boxed{\textbf{(C)}\ 65}$.

Adjacency restrictions on a binary string translate into a small alphabet of allowed blocks; the string becomes a word over that alphabet, and counting words of a given total length is a binomial-coefficient sum (a composition of $18$ into parts $2$ and $3$). Whenever "no two consecutive" and "no three consecutive" appear together, look for a block decomposition before setting up a recurrence.

Let $a_n$ be the number of valid strings of length $n$. Removing the final $10$ or $110$ gives $a_n = a_{n-2} + a_{n-3}$, with $a_1 = 1$, $a_2 = 0$, $a_3 = 1$. Then $1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65$, so $a_{19} = 65$.

• Writing the recurrence as Fibonacci (a_n = a_{n-1} + a_{n-2}) and getting a wrong count, or forgetting the block '110' and allowing '1110'.
• Off-by-one in the length equation (using $2k + j = 19$ instead of accounting for the leading $0$), which shifts the binomial sums and gives $60$ or $70$.