Inclusion-Exclusion

What you need to know

• Two groups. (number in $A$ or $B$) $=$ (number in $A$) $+$ (number in $B$) $-$ (number in both). Things in both were counted twice, so subtract them once. Example: from $1$ to $60$ there are $15$ multiples of $4$, $10$ of $6$, and $5$ of both (the multiples of $12$). So $15+10-5 = 20$ are multiples of $4$ or $6$.
• Three groups. Add the three groups, subtract the three overlaps of two groups, then add back the overlap of all three. Writing $\#(\ )$ for "the number in": $\#(A\text{ or }B\text{ or }C) = \#(A)+\#(B)+\#(C)-\#(A\text{ and }B)-\#(A\text{ and }C)-\#(B\text{ and }C)+\#(A\text{ and }B\text{ and }C)$. Example: from $1$ to $100$, the multiples of $2$, $3$, or $5$ number $50+33+20-16-10-6+3 = 74$.
• Any number of groups. This is the Principle of Inclusion-Exclusion (PIE): add the single groups, subtract the overlaps of two, add the overlaps of three, and so on, switching signs each time.
• Counting "none." The number in none of the groups is the total minus the number in at least one. Example: $100-74 = 26$ numbers from $1$ to $100$ are divisible by none of $2$, $3$, $5$.
• Counting multiples. From $1$ to $N$ there are $\lfloor N/m\rfloor$ multiples of $m$, where $\lfloor\ \rfloor$ means "round down." A number is a multiple of both $a$ and $b$ exactly when it is a multiple of $\text{lcm}(a,b)$. Example: from $1$ to $100$ there are $\lfloor 100/6\rfloor = 16$ multiples of $6$.
• Filling in a Venn diagram. Start with the innermost region and work outward. Example: in a class of $45$, $30$ take math, $20$ take science, and $10$ take both. Put $10$ in the middle, $30-10 = 20$ in "math only," $20-10 = 10$ in "science only," and $45-40 = 5$ outside.

How AMC 10 tests it

• Problems 5–12: survey problems ("$30$ take math, $20$ take science, $10$ take both") asking how many take neither, or how many are in exactly one group.
• Problems 10–18: whole numbers up to $N$ divisible by at least one of several numbers, or by none.
• Problems 15–22: PIE hidden inside arrangements ("every color is used," "at least one letter in its original spot").
• Sometimes an "exactly two" region, where the "or" formula is not enough and you must fill in the diagram.

Standard approaches

1. Draw the Venn diagram and fill it in from the center out; many problems need no formula.
2. For "at least one," find the "or" count. For "none," subtract it from the total.
3. For divisibility, each term is $\lfloor N/\text{lcm}\rfloor$.
4. For "every box gets used," count all ways, then subtract the ways that miss a box. With $n$ different objects and $k$ different boxes: $k^n-\binom{k}{1}(k-1)^n+\binom{k}{2}(k-2)^n-\cdots$. Example: $4$ different balls in $3$ boxes, none empty: $3^4-3\cdot2^4+3\cdot1^4 = 81-48+3 = 36$.
5. Check that every region is a whole number that is zero or positive. A negative region means you misread something.

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.

Step 1: divisible by $4$ or $6$. There are $\lfloor 600/4\rfloor = 150$ multiples of $4$ and $\lfloor 600/6\rfloor = 100$ multiples of $6$. Both means a multiple of $\text{lcm}(4,6) = 12$: $\lfloor 600/12\rfloor = 50$. By PIE, $150+100-50 = 200$.

Step 2: which of these are divisible by $9$? Divisible by $4$ and $9$ means a multiple of $\text{lcm}(4,9) = 36$. Divisible by $6$ and $9$ means a multiple of $\text{lcm}(6,9) = 18$. Every multiple of $36$ is a multiple of $18$, so count the multiples of $18$: $\lfloor 600/18\rfloor = 33$ (since $18\cdot33 = 594$).

Step 3: subtract. $200-33 = 167$.

The answer is $\boxed{\textbf{(B)}\ 167}$.

Pitfalls

• Subtracting the overlaps of two groups but forgetting to add back the overlap of all three.
• Reading "$10$ take both" as the "exactly these two" region when it also includes people in the third group, or the other way around.
• Using $\lfloor N/(ab)\rfloor$ instead of $\lfloor N/\text{lcm}(a,b)\rfloor$ when $a$ and $b$ share a factor. From $1$ to $60$, $5$ numbers are multiples of both $4$ and $6$, not $\lfloor 60/24\rfloor = 2$.
• Giving the "at least one" count when the question asks for "none," or the other way around.

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)