2012 AMC 12B Problem 12

Question

How many sequences of zeros and/or ones of length

20

have all the zeros consecutive, or all the ones consecutive, or both?

190

192

211

380

382

Let

A

be the sequences with all zeros together and

B

those with all ones together, then use

|A\cup B|=|A|+|B|-|A\cap B|

A sequence with the zeros together is fixed by choosing the first and last zero positions, giving

1+20+\binom{20}{2}

of them

Let

A

be the sequences in which all zeros are consecutive and

B

those in which all ones are consecutive.

For

A,

there is one all-ones sequence,

20

sequences with exactly one zero, and

\binom{20}{2}=190

sequences with two or more zeros (choose the first and last zero position). So

|A|=1+20+190=211,

and by symmetry

|B|=211.

A sequence in

A\cap B

is a block of zeros followed by a block of ones, or the reverse; there are

|A\cap B|=40

of these.

Therefore

|A\cup B|=211+211-40

=382.

Thus, the correct answer is E.

Problem 12 in other years