Question

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?

$55$

$60$

$65$

$70$

$75$

Answer: C

Concepts:partitions and compositions combinations casework

Difficulty rating: 2050

Solution:

No two $0$ s are adjacent, so the $0$ s are separated by blocks of $1$ s, each of size $1$ or $2$ (never $3$ ). If there are $k$ zeros, there are $k-1$ such blocks summing to $19-k$ ones.

The number of size- $2$ blocks is $(19-k)-(k-1)=20-2k,$ which must satisfy $0\le20-2k\le k-1,$ i.e. $7\le k\le10.$

Summing $\binom{k-1}{20-2k}$ over $k=7,8,9,10$ gives $\binom66+\binom74+\binom82+\binom90$ $=1+35+28+1$ $=65.$

Thus, C is the correct answer.

2019 AMC 12B Problem 23

Answer: C

Difficulty rating: 2050

Solution:

Problem 23 in Other Years