2019 AMC 10B Problem 25

The rules say what can sit between two $0$s, so cut the string at its $0$s.

Step 1: the building blocks.

1. Two $0$s can never be next to each other, so between neighboring $0$s there is at least one $1$.
2. There are never three $1$s in a row, so between neighboring $0$s there are at most two $1$s.
3. The string starts and ends with $0$. So after the first $0$, it is a chain of blocks, each block being $10$ or $110$. For example, $0\,10\,110\,10$ is the string $01011010$.

Step 2: how many blocks?

4. Say there are $k$ blocks, and $j$ of them are the long block $110$. The short blocks have $2$ digits and the long ones $3$, so the total length is
$$1 + 2k + j = 19, \quad\text{so}\quad j = 18 - 2k.$$
5. The number of long blocks is between $0$ and $k$. So $18 - 2k \ge 0$ means $k \le 9$, and $18 - 2k \le k$ means $k \ge 6$.

Step 3: count the arrangements. For each $k$, choose which $j$ of the $k$ block positions hold the long blocks.

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

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

Rules like "no two $0$s in a row" and "no three $1$s in a row" limit what can appear between the $0$s. That turns the string into a chain of a few allowed blocks, and counting chains of a given length is just choosing where the long blocks go. Look for this block picture before writing a long list.

Let $a_n$ count the good strings of length $n$. Every good string longer than $1$ ends with the block $10$ or $110$, and removing it leaves a shorter good string. So $a_n = a_{n-2} + a_{n-3}$, starting from $a_1 = 1$ (the string $0$), $a_2 = 0$, $a_3 = 1$ (the string $010$). The values for $n = 1, 2, \ldots, 19$ are
$$1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65.$$
So $a_{19} = 65$.

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}$.