Inclusion-Exclusion

Out of 100 job applicants, 60 know Python, 45 know C++, and 25 know both. How many know neither?

Have a go before reading on. The trap is adding $60 + 45 = 105$ and concluding more people know a language than applied — a warning sign you've double-counted, not a paradox.

Why plain addition breaks

If you just add the Python group and the C++ group, anyone who knows both languages gets counted twice — once in each group. The 25 people who know both are hiding inside both the 60 and the 45. To get the true count of "knows at least one language," you have to subtract that double-counted overlap back out once:

$|A \cup B| = |A| + |B| - |A \cap B|$

In words: the size of "A or B" equals the size of A, plus the size of B, minus whatever you counted twice, which is exactly "A and B."

Solving the applicants puzzle

$|A \cup B| = 60 + 45 - 25 = 80$

Eighty applicants know at least one language. Since there are 100 applicants total, $100 - 80 = \textbf{20}$ know neither. Quick sanity check: the "both" group of 25 can't exceed either individual group (25 ≤ 60 and 25 ≤ 45, fine), and 80 knowing at least one out of 100 total is plausible, not absurd.

Scaling to three sets

Same 100 applicants: 60 know Python, 45 know C++, 40 know Java. 25 know Python and C++, 20 know Python and Java, 15 know C++ and Java, and 10 know all three. How many know at least one language?

With three sets the pairwise subtraction over-corrects: subtracting all three pairwise overlaps removes the "all three" group three times (once inside each pair), on top of the three times it was added by the singles — so it needs to be added back exactly once to land on "counted once." The formula extends by alternating signs:

$|A \cup B \cup C| = |A|+|B|+|C| - |A\cap B|-|A\cap C|-|B\cap C| + |A\cap B\cap C|$

Plugging in: $60 + 45 + 40 - 25 - 20 - 15 + 10 = 95$. So 95 applicants know at least one language, leaving $100 - 95 = \textbf{5}$ who know none.

Trace one person through the formula to see why this works. Someone who knows all three languages gets added once in each of the three singles ($+3$), subtracted once in each of the three pairs ($-3$), and added back once in the triple term ($+1$) — net contribution $3 - 3 + 1 = 1$, counted exactly once, as required. Someone in exactly two groups: added twice ($+2$), subtracted once for the one pair they're in ($-1$), not in the triple term — net $2 - 1 = 1$. Someone in exactly one group: added once, in no pair, not in the triple — net $1$. Every person, regardless of how many sets they sit in, nets to exactly 1. That's the whole proof, and it's why the pattern of alternating $+, -, +, -, \ldots$ continues cleanly to any number of sets.

Where it shows up beyond Venn diagrams

Inclusion-exclusion is the standard tool for counting "at least one of these bad things happens," which is everywhere in probability puzzles: the probability that at least one of several dice shows a 6, that at least one collision happens in a hashing scheme, or — the canonical example — the derangement problem (how many ways can $n$ people mismatch $n$ labeled hats so that nobody gets their own), which is solved by inclusion-exclusion over the "person $i$ gets their own hat" events. Any time a direct count is easier to get wrong than right because of overlaps, the reflex should be: count the singles, subtract the pairs, add the triples, and stop when the terms run out.