Practice Maths

Inclusion–Exclusion and Pigeonhole Principles

← Back to Combinatorics›Specialist Maths

Key Terms

Inclusion-exclusion (2 sets)
|A ∪ B| = |A| + |B| − |A ∩ B|; subtract the overlap to avoid double-counting.
Inclusion-exclusion (3 sets)
|A ∪ B ∪ C| = |A|+|B|+|C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|.
Pigeonhole principle
If n items are placed into k containers and n > k, at least one container holds ≥ 2 items.
Generalised pigeonhole
If n items in k containers, at least one container holds at least ⌈n/k⌉ items (⌈⌉ = ceiling function).
Derangement
An arrangement of n objects where NO object appears in its original position.
When to use inclusion-exclusion
Use when you have overlapping sets and need the size of their union; subtract overlap once to avoid double-counting.

Inclusion–Exclusion Principle

Two sets:   |A ∪ B| = |A| + |B| − |A ∩ B|

Three sets:

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

Pigeonhole Principle: If n+1 objects are placed into n containers, at least one container holds ≥ 2 objects.

Generalised Pigeonhole: If kn+1 objects are placed into n containers, at least one container holds ≥ k+1 objects.

PrincipleWhen to UseKey Phrase
Inclusion–Exclusion (2 sets)Counting elements in A OR B when they overlap“at least one of”, “either … or …”
Inclusion–Exclusion (3 sets)Three overlapping categories“takes at least one of three subjects”
PigeonholeProving that some grouping must exceed a threshold“must”, “guaranteed”, “at least”

Worked Example 1 — Students Taking Maths or English

In a class of 50 students, 30 take Maths, 25 take English, and 12 take both. How many take at least one of these subjects?

|M ∪ E| = |M| + |E| − |M ∩ E| = 30 + 25 − 12

= 43 students

Worked Example 2 — Pigeonhole: Shared Birth Month

In a group of 13 people, prove that at least two share a birth month.

There are 12 months (containers) and 13 people (objects). By the pigeonhole principle, at least one month contains ≥ 2 people. Therefore at least two people share a birth month. □

Worked Example 3 — Generalised Pigeonhole

Five points are placed inside (or on the boundary of) a 2 × 2 square. Show that at least two points are within distance √2 of each other.

Divide the square into four 1 × 1 unit squares (the 4 containers). With 5 points (objects), by the pigeonhole principle, at least one unit square contains ≥ 2 points. The maximum distance between two points within a 1 × 1 square is the diagonal = √(12 + 12) = √2. So those two points are within distance √2 of each other. □

Hot Tip — Inclusion–Exclusion Pattern: Add individual sets, subtract pairwise intersections, add triple intersections. The signs alternate: +, −, +. For n sets, the formula has 2n − 1 terms total.

Why Does Inclusion–Exclusion Work?

When we compute |A| + |B|, every element in A ∪ B is counted, but elements in A ∩ B (both A and B) are counted twice — once for A and once for B. To correct the overcount, we subtract |A ∩ B| once:

|A ∪ B| = |A| + |B| − |A ∩ B|

For three sets, the argument is similar but requires more care. Adding |A|+|B|+|C| counts elements in exactly two sets twice and elements in all three sets three times. Subtracting |A∩B|+|A∩C|+|B∩C| removes the double-counted pairs, but also removes the triple-counted element once too many. Adding back |A∩B∩C| corrects this:

|A∪B∪C| = |A|+|B|+|C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|

You can verify: any element in exactly one set is counted 1−0+0 = 1 time; in exactly two sets: 2−1+0 = 1 time; in all three: 3−3+1 = 1 time. ✓

Complementary Approach to Inclusion–Exclusion

Sometimes it is easier to find |A ∪ B|’s complement. The number of elements in neither A nor B is:

|Total| − |A ∪ B| = |Total| − |A| − |B| + |A ∩ B|

Switch between direct and complementary methods depending on which intersection data is given.

The Pigeonhole Principle — Proof

Suppose we have n+1 objects in n containers. Assume for contradiction that every container holds at most 1 object. Then the total number of objects is at most n × 1 = n, contradicting the fact that there are n+1 objects. Therefore, at least one container holds ≥ 2 objects. □

Generalised version: If kn+1 objects are in n containers, at least one holds ≥ k+1. (Assume each holds at most k: maximum total is kn < kn+1, a contradiction.)

Choosing Pigeons and Holes

The skill in applying the pigeonhole principle lies in correctly identifying:

• The objects (“pigeons”): the items being distributed.

• The containers (“holes”): the categories they fall into.

Often you must construct the containers cleverly — e.g., dividing a geometric region, grouping numbers by remainder, or grouping people by a characteristic.

Example: Among any 5 integers, at least two have the same remainder when divided by 4. Why? There are 4 possible remainders (0, 1, 2, 3) and 5 integers, so by the pigeonhole principle, two integers share a remainder — meaning their difference is divisible by 4.

Inclusion–Exclusion with Counting Restrictions

Inclusion–exclusion can also be used in reverse: if you know |A ∪ B|, |A|, and |B|, you can find |A ∩ B| = |A| + |B| − |A ∪ B|. This is useful when a problem gives you the union and asks for the intersection (or vice versa).

Mastery Practice

  1. Fluency

    Q1 — Inclusion–Exclusion: Two Sets

    In a survey of 80 people, 55 own a dog, 40 own a cat, and 20 own both a dog and a cat. How many people own at least one of the two animals?

  2. Fluency

    Q2 — Finding the Intersection

    In a class of 35, every student studies at least one of Music or Art. 22 study Music and 19 study Art. How many study both?

  3. Fluency

    Q3 — Basic Pigeonhole

    (a) A bag contains red, blue and green socks. What is the minimum number of socks you must draw (without looking) to guarantee you have a matched pair?    (b) There are 366 people in a room. Prove that at least two share the same birthday.

  4. Fluency

    Q4 — Integers and Remainders

    Prove that among any 6 integers, at least two have the same remainder when divided by 5.

  5. Understanding

    Q5 — Inclusion–Exclusion: Three Sets

    In a group of 100 students: 60 study Maths, 50 study Science, 40 study English. Also: 25 study Maths and Science, 20 study Maths and English, 15 study Science and English, and 10 study all three. How many students study at least one subject?

  6. Understanding

    Q6 — Cards in a Deck

    From a standard 52-card deck, how many cards are either red or a face card (Jack, Queen, King)? (There are 26 red cards and 12 face cards; 6 face cards are red.)

  7. Understanding

    Q7 — Generalised Pigeonhole

    (a) In a class of 30 students, at least how many must share the same birth month?    (b) If 25 books are distributed among 6 shelves, prove that at least one shelf holds at least 5 books.

  8. Understanding

    Q8 — Only Some or Neither

    In a year group of 120 students: 80 play sport, 65 play a musical instrument, and 30 do neither. How many play both sport and an instrument?

  9. Problem Solving

    Q9 — Points in a Triangle

    An equilateral triangle has side length 2. Show that if 10 points are placed inside (or on the boundary of) the triangle, at least two points are within distance 1 of each other.

  10. Problem Solving

    Q10 — Three Sets with Unknowns

    A survey of 200 people found: 120 use social media daily, 90 watch TV daily, 80 read news daily. 45 do both social media and TV, 35 do both social media and news, 30 do both TV and news. 15 do all three. How many do none of the three?

See Answers ➔