Counting without double counting
Tonight's idea
A class of 30. Eighteen play football, fifteen play chess, and seven do both. How many play neither? If you add 18 and 15 you get 33, more than the class. The seven who do both were counted twice, once in each group. Take them off once: \(18 + 15 - 7 = 26\) play at least one, so 4 play neither.
That is inclusion–exclusion. For two groups \(A\) and \(B\), write \(|A|\) for the number in \(A\), \(A \cup B\) ("A or B") for everyone in at least one group, and \(A \cap B\) ("A and B") for everyone in both:
\[|A \cup B| = |A| + |B| - |A \cap B|\]Include both, exclude the overlap. With three groups it is a see-saw: add the three singles, subtract the three pairs, add back the triple overlap, because anyone in all three was added three times, subtracted three times, and needs to come back once:
\[|A \cup B \cup C| = |A|+|B|+|C| - |A\cap B| - |A\cap C| - |B \cap C| + |A \cap B \cap C|\]Now the strange fact. Five people check their hats at a party. The hats are handed back at random. What is the chance nobody gets their own hat? With 2 people it is \(\tfrac12\). With 3, \(\tfrac13\). With 4, \(\tfrac38 = 0.375\). With 5, \(\tfrac{11}{30} \approx 0.367\). And then it stops moving: with 10 people, or 100, or a million, the answer is 0.3679... A mix-up of hats is called a derangement, and inclusion–exclusion is how you count them, as the example shows.
Watch one: three hats
People 1, 2, 3 with hats 1, 2, 3. List every way of handing hats back (person 1 gets the first listed hat, and so on): 123, 132, 213, 231, 312, 321. Six ways.
Cross out any arrangement where someone gets their own hat. 123 (everyone does), 132 (person 1), 213 (person 3), 321 (person 2). That leaves 231 and 312: two derangements out of six, probability \(\tfrac{2}{6} = \tfrac13\).
By inclusion–exclusion instead: 6 arrangements, minus those where person 1 is right (2, because the other two hats can go either way round), person 2 is right (2), person 3 is right (2), plus back the pairs (1 each, three pairs), minus the triple (1): \(6 - 6 + 3 - 1 = 2\). Same answer, and this way works for a million people without listing anything.
Your turn
- In a school of 200, 120 take the bus, 60 take a packed lunch, and 35 do both. How many do neither?
- Of the numbers 1 to 100, how many are divisible by 2 or by 3? (Count multiples of 2, multiples of 3, and multiples of 6.)
- Of the numbers 1 to 100, how many are divisible by 2, 3 or 5? You will need all three pair overlaps (multiples of 6, 10, 15) and the triple (multiples of 30).
- How many numbers from 1 to 1000 are divisible by neither 2 nor 5? (Find how many are divisible by at least one, then subtract from 1000.)
- A survey of 50 students claims 30 like pizza, 25 like pasta, and 3 like both. Explain why these numbers cannot all be true.
- List every derangement of the letters ABCD (every rearrangement where no letter is in its original place). There should be nine. Check: 9 out of 24 is \(\tfrac38\).
Stretch: why the see-saw works
Draw three overlapping circles A, B, C. They cut the page into eight regions (including the outside). For each region inside the circles, count how many times the formula \(|A|+|B|+|C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|\) counts a person standing there. For example, someone in A only is counted once by \(|A|\) and by nothing else. Someone in A and B but not C is counted by \(|A|\), \(|B|\) and \(|A \cap B|\): that is \(1 + 1 - 1 = 1\). Do all seven inside regions and show every person is counted exactly once. That is the whole proof.
Answers
- \(120 + 60 - 35 = 145\) do at least one, so 55 do neither.
- Multiples of 2: 50. Of 3: 33. Of 6: 16. \(50 + 33 - 16 = 67\).
- Singles: 50 + 33 + 20 = 103. Pairs: multiples of 6 (16), of 10 (10), of 15 (6): subtract 32. Triple: multiples of 30 (3): add 3. \(103 - 32 + 3 = 74\).
- Multiples of 2: 500. Of 5: 200. Of 10: 100. Divisible by at least one: \(500 + 200 - 100 = 600\). Neither: 400. (Or: in every block of ten, exactly 1, 3, 7, 9 qualify, 4 out of 10, so 400.)
- At least one of pizza or pasta: \(30 + 25 - 3 = 52\), more than the 50 students surveyed. Impossible.
- BADC, BCDA, BDAC, CADB, CDAB, CDBA, DABC, DCAB, DCBA. Nine.
Stretch. A only, B only, C only: counted once each. In exactly two circles, say A and B: \(1 + 1 - 1 = 1\). In all three: \(1+1+1 - 1 - 1 - 1 + 1 = 1\). Every region is counted exactly once, so the formula counts each person once, which is what \(|A \cup B \cup C|\) means.