2019 AMC 12B Problem 23

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

Show solution

Solution

No two

0

s are adjacent, so the

0

s are separated by blocks of

1

s, each of size

1

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.

Tagged: partitions and compositions · combinations · casework