2019 AMC 12B Problem 23

Problem 23 of 25HarderCounting & Probability

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?

Show solution

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.

More practice

Concepts: partitions and compositions · combinations · casework

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.