Solutions — Inclusion–Exclusion and Pigeonhole Principles
-
Q1 — Inclusion–Exclusion: Two Sets
Let D = dog owners, C = cat owners. We are given |D| = 55, |C| = 40, |D ∩ C| = 20.
|D ∪ C| = |D| + |C| − |D ∩ C| = 55 + 40 − 20 = 75 people
People who own neither: 80 − 75 = 5.
-
Q2 — Finding the Intersection
Since every student studies at least one subject, |M ∪ A| = 35.
Applying inclusion–exclusion:
|M ∪ A| = |M| + |A| − |M ∩ A|
35 = 22 + 19 − |M ∩ A|
|M ∩ A| = 41 − 35 = 6 students study both Music and Art.
-
Q3 — Basic Pigeonhole
(a) There are 3 colours (containers). In the worst case, you draw one of each colour first (3 socks), none matching. The 4th sock must match one already drawn.
You need to draw 4 socks to guarantee a matched pair.
(b) There are at most 366 distinct birthdays in a year (containers). With 366 people (objects), by the pigeonhole principle, at least one birthday has ≥ 2 people.
Therefore at least two people share the same birthday. □
-
Q4 — Integers and Remainders
The possible remainders on division by 5 are {0, 1, 2, 3, 4} — five categories (containers).
We have 6 integers (objects). Since 6 > 5, by the pigeonhole principle, at least two integers must fall into the same remainder category.
That is, at least two of the six integers have the same remainder when divided by 5. □
Consequence: the difference of those two integers is divisible by 5.
-
Q5 — Inclusion–Exclusion: Three Sets
|M ∪ S ∪ E| = |M| + |S| + |E| − |M∩S| − |M∩E| − |S∩E| + |M∩S∩E|
= 60 + 50 + 40 − 25 − 20 − 15 + 10
= 150 − 60 + 10
= 100 students
This equals the total group size, so every student studies at least one subject.
-
Q6 — Cards in a Deck
|Red ∪ Face| = |Red| + |Face| − |Red ∩ Face|
The 6 red face cards (J, Q, K of Hearts and Diamonds) are in both sets.
= 26 + 12 − 6 = 32 cards are either red or a face card (or both).
-
Q7 — Generalised Pigeonhole
(a) 30 students, 12 months. By the generalised pigeonhole principle:
Minimum guaranteed maximum = ⌈30/12⌉ = ⌈2.5⌉ = 3.
At least one birth month is shared by ≥ 3 students.
Proof by contradiction: if every month had ≤ 2 students, total ≤ 24 < 30.
(b) 25 books, 6 shelves. Assume each shelf holds ≤ 4 books: maximum total = 24 < 25, a contradiction.
Therefore at least one shelf holds ≥ 5 books. □
-
Q8 — Only Some or Neither
Students doing at least one activity = 120 − 30 = 90.
|S ∪ M| = |S| + |M| − |S ∩ M|
90 = 80 + 65 − |S ∩ M|
|S ∩ M| = 145 − 90 = 55 students play both sport and instrument.
Check: only sport = 80 − 55 = 25; only instrument = 65 − 55 = 10; both = 55; neither = 30. Total = 25+10+55+30 = 120. ✓
-
Q9 — Points in a Triangle
Construction: Divide the equilateral triangle with side 2 into 9 congruent equilateral triangles, each with side length 2/3.
Containers: The 9 smaller triangles (9 regions).
Objects: 10 points.
Since 10 > 9, by the pigeonhole principle, at least one small triangle contains ≥ 2 of the 10 points.
The maximum distance between any two points within a small equilateral triangle of side 2/3 is the length of its longest chord, which is 2/3 < 1.
Therefore, at least two of the 10 points are within distance 2/3 < 1 of each other. □
-
Q10 — Three Sets with Unknowns
|S ∪ T ∪ N| = |S| + |T| + |N| − |S∩T| − |S∩N| − |T∩N| + |S∩T∩N|
= 120 + 90 + 80 − 45 − 35 − 30 + 15
= 290 − 110 + 15 = 195
People who do none of the three = 200 − 195 = 5 people.