AMC 10 · 2012 · #12

Grade 7 counting

Archetype Overlap / Complement Counting └ Sub-archetype Two-Set Inclusion-Exclusion: Solve for Missing Region

principle-of-inclusion-exclusioncombinations-basicsymmetry-argumentconsecutive-integer-count systematic-enumerationidentify-subproblemseasier-related-problem ↑ Prerequisites: principle-of-inclusion-exclusioncombinations-basic

📏 Long solution 💡 3 insights

Problem

All of one symbol must sit in one unbroken block, or all of the other, or both. Count the sequences.

Pick an answer.

(A)

190

(B)

192

(C)

211

(D)

380

(E)

382

How to solve

Strategy Make a Systematic List

The phrase "all the zeros are consecutive" is really a statement about positions: the zeros occupy one unbroken stretch of seats. Once it is read that way, a whole sequence is pinned down by where that stretch starts and stops, so the counting becomes an orderly list of block placements. Two such lists are needed, one for the zeros and one for the ones, and the sequences appearing in both lists have to be subtracted once. Everything then turns on getting that overlap exactly right rather than estimating it, and on deciding openly whether the two all-same sequences belong, because those two sequences are precisely what separates two of the listed values.

1STEP 1

Turn the wording into positions

A block is just a range of positions.

{seats holding 0} = {i, i+1, …, j}, 1 ≤ i ≤ j ≤ 20

2STEP 2

List the zero-block sequences by block length

Counting by block length is straightforward.

k = 1, 2, …, 19 ⟹ 21-k placements each

3STEP 3

Add the placements

The placements add to 209.

20 + 19 + … + 2 = (20 · 21)/2 - 1 = 210 - 1 = 209

4STEP 4

The ones come free by flipping

Swapping the symbols gives the other case free.

0 ⇔ 1 is its own inverse ⟹ #{ones consecutive} = #{zeros consecutive} = 209

5STEP 5

Pin down the overlap exactly

The overlap is exactly 38 sequences.

0…0_a1…1₂₀-a or 1…1_a0…0₂₀-a, a = 1, …, 19 ⟹ 19 + 19 = 38

6STEP 6

Add the two piles, give back the overlap

Adding and giving back gives 380.

209 + 209 - 38 = 418 - 38 = 380

7STEP 7

Settle the two all-same sequences

The all-one-symbol cases are excluded, choice (B).

380 (both symbols required) versus 380 + 2 = 382 (constant sequences admitted)

Answer

380

Run the identical argument on a row of 4 seats, where the whole list can be checked by hand. Zeros consecutive: block lengths 1, 2, 3 give 4 + 3 + 2 = 9 sequences; ones consecutive gives 9; the overlap is 0111, 0011, 0001, 1000, 1100, 1110, which is 3 + 3 = 6; total 9 + 9 - 6 = 12. Checking directly, there are 16 sequences of length 4, of which 14 contain both symbols, and exactly two of those fail, namely 0101 and 1010, leaving 12. The methods agree. Running the same argument for a row of n seats gives 2((n(n+1))/2 - 1) - 2(n-1) = n² - n = n(n-1), which returns 4 · 3 = 12 at n = 4 and 20 · 19 = 380 at n = 20. That closed form also exposes the near misses among the choices: n(n-1) = 2C(20, 2) = 2 · 190, so 190 is the answer halved, 211 is 210 + 1, the size of a single collection when the all-same sequence is wrongly kept, and 382 is 380 plus the two constant sequences. The total is also sane in scale: only about 380 of 2²⁰ ≈ 1,048,576 sequences qualify, which fits the fact that demanding one unbroken block is a severe restriction.

💡Key takeaway

"All the zeros together" just means the zeros fill one stretch of seats, so counting the sequences is counting where that stretch starts and stops, and the only sequences counted twice are the ones made of a block of zeros sitting right next to a block of ones.

Turn the wording into positions
List the zero-block sequences by block length
Add the placements
The ones come free by flipping
Pin down the overlap exactly
Add the two piles, give back the overlap
Settle the two all-same sequences