Sets, overlaps and worst cases

Two sets: add, then remove the double count

When two groups overlap, adding their sizes counts everyone in the overlap twice, so take the overlap off once:

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

Here $|A \cup B|$ is the number in at least one group and $|A \cap B|$ the number in both. Many questions also mention people in neither group, so write the whole population as

$$\text{Total} = |A| + |B| - \text{Both} + \text{Neither}.$$

Any one of the five numbers follows from the other four. Of 40 students, if 25 take finance, 18 take marketing and 7 take both, then $25 + 18 - 7 = 36$ take at least one and $40 - 36 = 4$ take neither. The same rule for probabilities is in counting and probability.

A two-way table does the same job and makes the "only" groups visible. Every row and column must add up, so a missing cell can be filled from the others:

	Marketing	No marketing	Total
Finance	7	18	25
No finance	11	4	15
Total	18	22	40

Three sets: inclusion–exclusion

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

Follow one person who belongs to all three groups. The first three terms count them three times. They also sit in all three pairwise overlaps, so the subtractions remove them three times, leaving zero; adding $|A \cap B \cap C|$ brings the count back to one. A person in exactly two groups is counted twice and subtracted once, which is right.

In this formula $|A \cap B|$ means everyone in both A and B, including those also in C. A question that says "15 firms export to France and Germany" normally means this whole overlap; "only to France and Germany" or "to exactly these two" means the part outside the centre.

Exactly one, exactly two, all three

Split everyone in at least one group into layers: $E_1$ people in exactly one group, $E_2$ in exactly two and $E_3$ in all three. Then:

• counting people, $E_1 + E_2 + E_3 = \text{Total} - \text{None}$;
• counting memberships, $|A| + |B| + |C| = E_1 + 2E_2 + 3E_3$, because each person is counted once for every group they are in.

Subtracting the first line from the second gives $|A| + |B| + |C| - (\text{Total} - \text{None}) = E_2 + 2E_3$, which rearranges to

$$\text{Total} - \text{None} = |A| + |B| + |C| - (\text{exactly two}) - 2 \times (\text{all three}).$$

The sum of the three groups holds one extra copy of each exactly-two person and two extra copies of each all-three person; the formula removes exactly those copies. Use it when a question gives or asks for "exactly two"; use inclusion–exclusion when it gives pairwise "both" counts. The two connect because the three pairwise counts add up to $E_2 + 3E_3$: an all-three person sits in all three pairs.

Filling a Venn diagram from the centre out

Three circles make seven regions, plus the outside for "none". When the pairwise counts are given, fill the regions in this order:

1. The centre: all three.
2. Each pair-only region: the pairwise count minus the centre.
3. Each single-only region: the group's total minus its two pair-only regions and the centre.
4. None: the total minus all seven regions.

Each step uses only numbers already found, so nothing is taken off twice. Starting from a group's total instead forces a guess about how much of it lies in the overlaps. Before answering, check that every region is zero or more and that the seven regions add up to the union given by the formula.

How small or large can an overlap be?

Sometimes only the group sizes are known. If 70 of 100 people like A and 60 like B, at least $70 + 60 - 100 = 30$ like both, because 130 memberships cannot fit into 100 people otherwise; and at most 60 do, when the smaller group lies entirely inside the larger. In general

$$\max(0,\ |A| + |B| - \text{Total}) \le \text{Both} \le \min(|A|, |B|).$$

Worst cases and guarantees

"How many must be drawn to be sure of…" asks about the worst possible luck, not the average. Build the largest selection that still fails, then add one: the next item cannot avoid success. This is the pigeonhole principle: put more items than boxes into boxes, and some box holds at least two.

• To be sure of $k$ of the same kind among $m$ kinds, the worst case holds $k - 1$ of each, so $(k - 1)m + 1$ draws are needed. With 4 kinds, 3 of one kind needs $2 \times 4 + 1 = 9$ draws.
• A scarce kind caps the worst case. A kind with fewer than $k - 1$ items can contribute only what it has. Add up what each kind can give without reaching $k$, then add one.
• To be sure of a particular kind, the worst case takes every item of the other kinds first.

Test the answer by trying to build a failing selection of that size. If none exists, and one item fewer can fail, the answer is right.