# 2019 AMC 10B Problems/Problem 25

The following problem is from both the 2019 AMC 10B #25 and 2019 AMC 12B #23, so both problems redirect to this page.

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

$\textbf{(A) }55\qquad\textbf{(B) }60\qquad\textbf{(C) }65\qquad\textbf{(D) }70\qquad\textbf{(E) }75$

## Solution 1 (Recursion)

We can deduce, from the given restrictions, that any valid sequence of length $n$ will start with a $0$ followed by either $10$ or $110$. Let $f(n)$ be the number of valid (meaning: the sequence contains 0s and 1s, starts and ends with both 0, and there are no two consecutive 0s and no three consecutive 1s) sequences of length $n$.

Then we can define a recursive function $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 give conditions).

We derived the recursive function, since for any valid sequence of length $n$, you can append either $10$ or $110$ to return to the starting position, 0, and the resulting sequence will still satisfy 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 $\boxed{\text{\bf{(C)} } 65}$.

Contributors:

~Original Author

~BakedPotato66

## Solution 2 (casework)

After any particular $0$, the next $0$ in the sequence must appear exactly $2$ or $3$ positions down the line. In this case, we start at position $1$ and end at position $19$, i.e. we move a total of $18$ positions down the line. Therefore, we must add a series of $2$s and $3$s to get $18$. There are a number of ways to do this:

Case 1: nine $2$s - there is only $1$ way to arrange them.

Case 2: two $3$s and six $2$s - there are ${8\choose2} = 28$ ways to arrange them.

Case 3: four $3$s and three $2$s - there are ${7\choose4} = 35$ ways to arrange them.

Case 4: six $3$s - there is only $1$ way to arrange them.

Summing the four cases gives $1+28+35+1=\boxed{\textbf{(C) }65}$.

## Solution 3 (casework and blocks)

We can simplify the original problem into a problem where there are $2^{17}$ binary characters with zeros at the beginning and the end. Then, we know that we cannot have a block of 2 zeroes and a block of 3 ones. Thus, our only options are a block of $0$s, $1$s, and $11$s. Now, we use casework:

Case 1: Alternating 1s and 0s. There is simply 1 way to do this: $0101010101010101010$. Now, we note that there cannot be only one block of $11$ in the entire sequence, as there must be zeroes at both ends and if we only include 1 block, of $11$s this cannot be satisfied. This is true for all odd numbers of $11$ blocks.

Case 2: There are 2 $11$ blocks. Using the zeroes in the sequence as dividers, we have a sample as $0110110101010101010$. We know there are 8 places for $11$s, which will be filled by $1$s if the $11$s don't fill them. This is ${8\choose2} = 28$ ways.

Case 3: Four $11$ blocks arranged. Using the same logic as Case 2, we have ${7\choose4} = 35$ ways to arrange four $11$ blocks.

Case 4: No single $1$ blocks, only $11$ blocks. There is simply one case for this, which is $0110110110110110110$.

Adding these four cases, we have $1+28+35+1=\boxed{\textbf{(C) }65}$ as our final answer.

~Equinox8

## Solution 4 (similar to #3)

Any valid sequence must start with a $0$. We can then think of constructing a sequence as adding groups of terms to this $0$, each ending in $0$. (This is always possible because every valid string ends in $0$.) For example, we can represent the string $01011010110110$ as: $0-10-110-10-110-110$. To not have any consecutive 0s, we must have at least one $1$ before the next $0$. However, we cannot have three or more $1$s before the next $0$ because we cannot have three consecutive $1$s. Consequently, we can only have one or two $1$s.

So we can have the groups: $10$ and $110$.

After the initial $0$, we have $18$ digits left to fill in the string. Let the number of $10$ blocks be $x$, and $110$ be $y$. Then $x$ and $y$ must satisfy $2x+3y=18$. We recognize this as a Diophantine equation. Taking $\pmod{2}$ yields $y=0 \pmod{2}$. Since $x$ and $y$ must both be nonnegative, we get the solutions $(9, 0)$, $(6, 2)$, $(3, 4)$, and $(0, 6)$. We now handle each of these cases separately.

$(9, 0)$: Only one arrangement, namely all $10$s.

$(6, 2)$: We have 6 groups of $11$, and $2$ groups of $110$. This has $\binom{6+2}{2}=28$ cases.

$(3, 4)$: This means we have 3 groups of $10$, and 4 groups of $110$. This has $\binom{3+4}{3}=35$ cases.

$(0, 6)$: Only one arrangement, namely all $110$.

Adding these, we have $1+28+35+1=65 \longrightarrow \boxed{(C) 65}$. ~Math4Life2020

~edited by alpha_2 for spelling and and typos

## Solution 5 (Constructive Counting)

Suppose the number of $0$s is $n$. We can construct the sequence in two steps:

Step 1: put $n-1$ of $1$s between the $0$s;

Step 2: put the rest $19-n-(n-1)=20-2n$ of $1$s in the $n-1$ spots where there is a $1$. There are $\binom{n-1}{20-2n}$ ways of doing this.

Now we find the possible values of $n$:

First of all $n+(n-1) \leq 19 \Rightarrow n\leq 10$ (otherwise there will be two consecutive $0$s);

And secondly $20-2n \leq n-1\Rightarrow n\geq 7$ (otherwise there will be three consecutive $1$s).

Therefore the answer is $$\sum_{n=7}^{10} \binom{n-1}{20-2n} = \binom{6}{6} + \binom{7}{4} + \binom{8}{2} + \binom{9}{0} = \boxed{\textbf{(C) }65}.$$

~ asops

## Solution 6 (Recursion)

For a valid sequence of length $n$, the sequence must be in the form of $01xx...xx10$. By removing the $01$ at the start of the sequence and the $10$ at the end of the sequence, there are $n-4$ bits left. The $n-4$ bits left can be in the form of:

$0yy...yy0$, the whole $(n-4)$ bits are valid sequence, which is $f(n-4)$
$0yy...y01$, the $(n-5)$ bits before the last $1$ are valid sequence, which is $f(n-5)$
$10y...yy0$, the $(n-5)$ bits after the first $1$ are valid sequence, which is $f(n-5)$
$10y...y01$, the $(n-6)$ bits between the first and last $1$ are valid sequence, which is $f(n-6)$


So, $f(n) = f(n-4) + 2f(n-5) + f(n-6)$

We will calculate $f(19)$ by Dynamic Programming.

$f(3) = 1$

$f(4) = 1$

$f(5) = 1$

$f(6) = 2$

$f(7) = 2$

$f(8) = 3$

$f(9) = f(5) + 2 \cdot f(4) + f(3) = 1 + 2 \cdot 1 + 1 = 4$

$f(10) = f(6) + 2 \cdot f(5) + f(4) = 2 + 2 \cdot 1 + 1 = 5$

$f(11) = f(7) + 2 \cdot f(6) + f(5) = 2 + 2 \cdot 1 + 1 = 7$

$f(12) = f(8) + 2 \cdot f(7) + f(6) = 3 + 2 \cdot 2 + 2 = 9$

$f(13) = f(9) + 2 \cdot f(8) + f(7) = 4 + 2 \cdot 3 + 2 = 12$

$f(14) = f(10) + 2 \cdot f(9) + f(8) = 5 + 2 \cdot 4 + 3 = 16$

$f(15) = f(11) + 2 \cdot f(10) + f(9) = 7 + 2 \cdot 5 + 4 = 21$

$f(16) = f(12) + 2 \cdot f(11) + f(10) = 9 + 2 \cdot 7 + 5 = 28$

$f(17) = f(13) + 2 \cdot f(12) + f(11) = 12 + 2 \cdot 9 + 7 = 37$

$f(18) = f(14) + 2 \cdot f(13) + f(12) = 16 + 2 \cdot 12 + 9 = 49$

$f(19) = f(15) + 2 \cdot f(14) + f(13) = 21 + 2 \cdot 16 + 12 = \boxed{\text{\bf{(C)} } 65}$

We can further prove $f(n) = f(n-4) + 2f(n-5) + f(n-6)$ is equivalent to $f(n) = f(n-2) + f(n-3)$

Let $k(n) = f(n-2) + f(n-3)$

$k(n-2) = f(n-4) + f(n-5)$

$k(n-3) = f(n-5) + f(n-6)$

$k(n-2)+ k(n-3) = f(n-4) + 2f(n-5) + f(n-6) = f(n)$

$f(n) = k(n-2)+ k(n-3)$

$f(n-2) = k(n-4)+ k(n-5)$

$f(n-3) = k(n-5)+ k(n-6)$

$k(n) = f(n-2) + f(n-3) = k(n-4)+ k(n-5) + k(n-5)+ k(n-6) = k(n-4) + 2k(n-5) + k(n-6)$

So $k(n)$ is the same as $f(n)$.

~ pi_is_3.14

## Video Solution

For those who want a video solution: https://youtu.be/VamT49PjmdI