Inclusion-Exclusion

## What you need to know
- Two sets: $|A \cup B| = |A| + |B| - |A \cap B|$.
- Three sets: $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$.
- General principle: add the single sets, subtract pairwise intersections, add triple intersections, and so on with alternating signs.
- Complement form: elements in none of the sets number $N - |A \cup B \cup \cdots|$.
- Multiples of $m$ in $\{1, \dots, N\}$: $\lfloor N/m \rfloor$; multiples of both $a$ and $b$ are multiples of $\operatorname{lcm}(a,b)$.
- Venn-diagram bookkeeping: fill the innermost region first and work outward.

## How AMC 10 tests it
- Problems 5–12: survey problems ("$30$ take math, $20$ take science, $10$ take both") asking for the "neither" count or an "exactly one" region.
- Problems 10–18: integers up to $N$ divisible by at least one of several numbers, or by none.
- Problems 15–22: inclusion-exclusion hidden inside arrangements ("every color is used," "at least one letter in its original spot").
- Occasionally an "exactly two" region, where the union formula is not enough and the diagram must be filled.

## Standard approaches
1. Draw the Venn diagram and fill regions from the center; many problems need no formula.
2. For "at least one," compute the union; for "none," subtract the union from the total.
3. For divisibility, each term is $\lfloor N / \operatorname{lcm} \rfloor$.
4. For "every box used," count all assignments and subtract those missing a box: $k^n - \binom{k}{1}(k-1)^n + \binom{k}{2}(k-2)^n - \cdots$.
5. Check that every region is a nonnegative integer; a negative region means a misread.

## Worked example
How many positive integers at most $600$ are divisible by $4$ or $6$ but not by $9$?

(A) $150$ (B) $167$ (C) $178$ (D) $184$ (E) $200$

Solution. Divisible by $4$ or $6$: $\lfloor 600/4 \rfloor + \lfloor 600/6 \rfloor - \lfloor 600/12 \rfloor = 150 + 100 - 50 = 200$. Among these, remove those divisible by $9$: multiples of $\operatorname{lcm}(4,9) = 36$ or of $\operatorname{lcm}(6,9) = 18$. Every multiple of $36$ is a multiple of $18$, so this is just the multiples of $18$: $\lfloor 600/18 \rfloor = 33$. Answer $200 - 33 = 167$, so $\boxed{\textbf{(B)}\ 167}$.

## Pitfalls
- Subtracting the pairwise overlaps but forgetting to add the triple overlap back.
- Reading "$10$ take both" as an "exactly both" region when it includes the triple region (or the reverse).
- Using $\lfloor N/(ab) \rfloor$ instead of $\lfloor N/\operatorname{lcm}(a,b) \rfloor$ when $a$ and $b$ share a factor.
- Reporting the union when the question asks for the complement, or vice versa.

Traps that recur

• Adding the five box probabilities (5 · 1/25) without subtracting overlaps, or dropping the alternating signs in inclusion–exclusion. (2021 AMC 10B #22)
• Forgetting to add back the single arrangement with both red and blue empty (all candy in white), which gives 1931. (2010 AMC 10B #22)
• Subtracting all 400 multiples of 5 instead of only the multiples of 5 that are also multiples of 3 or 4. (2001 AMC 10 #25)
• Applying |A union B union C| = sum of singles minus pairs plus triple with the wrong meaning of the 9, which counts students in at least two classes, not pairwise overlaps. (2017 AMC 10B #13)