Skip to main content

2012 AMC 12B Problem 12

Problem 12 of 25IntermediateCombinatorics

How many sequences of zeros and/or ones of length 2020 have all the zeros consecutive, or all the ones consecutive, or both?

Answer choices

Show solution

Solution

Let AA be the sequences in which all zeros are consecutive and BB those in which all ones are consecutive. For A,A, there is one all-ones sequence, 2020 sequences with exactly one zero, and (202)=190\binom{20}{2}=190 sequences with two or more zeros (choose the first and last zero position). So ∣A∣=1+20+190=211,|A|=1+20+190=211, and by symmetry ∣B∣=211.|B|=211. A sequence in A∩BA\cap B is a block of zeros followed by a block of ones, or the reverse; there are ∣A∩B∣=40|A\cap B|=40 of these. Therefore ∣A∪B∣=211+211−40|A\cup B|=211+211-40 =382.=382. Thus, the correct answer is E.
AoPS wiki

Tagged: inclusion-exclusion · combinations

More practice