📘 1.5 The Pigeonhole Principle – simple but powerful
Hello students! Today’s topic is almost like a magic trick. The pigeonhole principle sounds too simple to be useful, yet it solves many surprising problems. If you have more pigeons than holes, at least one hole must have at least two pigeons. In Ethiopian exams, they love to ask: “minimum number to guarantee…” Let’s explore! 🇪🇹
👩🏫 Think of it this way: If 11 pigeons sit in 10 holes, then at least one hole has 2 or more pigeons. It’s obvious, but we can stretch it far.
🐦 Basic pigeonhole principle
📌 If \(n\) items are placed into \(m\) containers and \(n > m\), then at least one container contains two or more items.
╔═══════╗ ╔═══════╗ ╔═══════╗ ╔═══════╗
│ 🕊️ │ │ 🕊️ │ │ 🕊️ │ │ 🕊️ │
╚═══════╝ ╚═══════╝ ╚═══════╝ ╚═══════╝
hole 1 hole 2 hole 3 hole 4
we have 5 pigeons → one hole gets at least two.
📚 Example 1 (classic): In a department of 13 professors, at least two were born in the same month. Because 12 months (holes) and 13 professors (pigeons) → at least one month has ≥2.
🔢 Example 2 (pairs summing to 10): Take numbers from \(S=\{1,2,\dots,9\}\). How many numbers guarantee two sum to 10?
Pair the numbers: \(\{1,9\},\{2,8\},\{3,7\},\{4,6\},\{5\}\). These are our 5 “holes”. If we pick 6 numbers, by pigeonhole we pick both from some pair → sum 10. So answer = 6.
Pair the numbers: \(\{1,9\},\{2,8\},\{3,7\},\{4,6\},\{5\}\). These are our 5 “holes”. If we pick 6 numbers, by pigeonhole we pick both from some pair → sum 10. So answer = 6.
🐦 Generalized pigeonhole principle
📌 If \(N\) objects are placed into \(k\) boxes, then at least one box contains \(\lceil N/k \rceil\) or more objects.
📝 Example 3 (students in class): Minimum students to guarantee 3 are born in the same month?
\(k=12\) months. We want \(\lceil N/12\rceil \ge 3\). Smallest \(N\) such that \(N/12 > 2\) (i.e. \(N>24\)). So \(N = 25\) → \(\lceil 25/12\rceil = 3\). ✅
\(k=12\) months. We want \(\lceil N/12\rceil \ge 3\). Smallest \(N\) such that \(N/12 > 2\) (i.e. \(N>24\)). So \(N = 25\) → \(\lceil 25/12\rceil = 3\). ✅
✈️ Example 4 (from module): In a tournament with \(n\) players, each plays every other and each wins at least once. Show two players have same number of wins.
Possible win counts: \(1,2,\dots, n-1\) (that’s \(n-1\) possibilities). There are \(n\) players → pigeonhole: at least two share same win count.
Possible win counts: \(1,2,\dots, n-1\) (that’s \(n-1\) possibilities). There are \(n\) players → pigeonhole: at least two share same win count.
📌 Other classic examples from the module
🖐️ Example 5 (handshake / married couple): There are \(n\) married couples. How many people must we pick to guarantee a married couple?
Think: worst case we pick one from each couple → \(n\) people without a pair. Next (\(n+1\))th forces a couple. So answer = \(n+1\).
Think: worst case we pick one from each couple → \(n\) people without a pair. Next (\(n+1\))th forces a couple. So answer = \(n+1\).
💍 Example 6 (socks problem): A drawer has 6 blue socks and 4 white socks. How many socks to pull to guarantee a matching pair?
Worst case: first 2 are different colours (blue & white). Third sock must match one of them. So answer = 3. (Pigeonhole with colours as boxes.)
Worst case: first 2 are different colours (blue & white). Third sock must match one of them. So answer = 3. (Pigeonhole with colours as boxes.)
✍️ Exam‑style questions – test yourself
1️⃣ How many people must be in a room to guarantee at least two share the same birth‑day of the week (Mon‑Sun)?
A) 7 B) 8 C) 14 D) 6
Correct: B) 8
7 days (holes) → with 8 people (pigeons) at least two share same day.
7 days (holes) → with 8 people (pigeons) at least two share same day.
2️⃣ Minimum students to guarantee that 5 of them are in the same class (Freshman, Sophomore, Junior, Senior)?
A) 17 B) 20 C) 21 D) 16
Correct: A) 17
\(k=4\), want \(\lceil N/4\rceil \ge 5\). Smallest \(N\) such that \(N/4 > 4\) → \(N>16\) → \(N=17\).
\(k=4\), want \(\lceil N/4\rceil \ge 5\). Smallest \(N\) such that \(N/4 > 4\) → \(N>16\) → \(N=17\).
3️⃣ From the set \(\{1,2,3,\dots,9\}\), what is the minimum number of elements you must pick to guarantee that two of them add up to 10?
A) 5 B) 6 C) 7 D) 8
Correct: B) 6
Pairs: \(\{1,9\},\{2,8\},\{3,7\},\{4,6\},\{5\}\) (5 holes). Pick 6 → you must take both from some pair → sum 10.
Pairs: \(\{1,9\},\{2,8\},\{3,7\},\{4,6\},\{5\}\) (5 holes). Pick 6 → you must take both from some pair → sum 10.
4️⃣ A box has 8 blue socks and 8 red socks. How many socks must be drawn to guarantee a pair of the same colour?
A) 2 B) 3 C) 4 D) 5
Correct: B) 3
Two colours → worst case first two are different (blue & red). Third must match one → guaranteed pair.
Two colours → worst case first two are different (blue & red). Third must match one → guaranteed pair.
5️⃣ What is the minimum number of students needed to guarantee that 4 of them were born in the same month?
A) 37 B) 36 C) 48 D) 49
Correct: A) 37
\(k=12\), want \(\lceil N/12 \rceil \ge 4\) → \(N/12 > 3\) → \(N>36\) → \(N=37\).
\(k=12\), want \(\lceil N/12 \rceil \ge 4\) → \(N/12 > 3\) → \(N>36\) → \(N=37\).
6️⃣ 5 points are placed inside a square of side 2. Show that at least two points are at distance ≤ \(\sqrt{2}\). This uses pigeonhole by dividing the square into how many smaller squares?
A) 2 B) 4 C) 6 D) 8
Correct: B) 4
Divide into 4 unit squares (pigeonholes). 5 points → one square gets ≥2 points; max distance in unit square = diagonal \(\sqrt{2}\).
Divide into 4 unit squares (pigeonholes). 5 points → one square gets ≥2 points; max distance in unit square = diagonal \(\sqrt{2}\).
📚 Exercise 1.5 – selected answers from the module
| Exercise (module) | Answer / explanation |
|---|---|
| 68 (a). Minimum students to guarantee 4 born same day of week. | k=7, want ⌈N/7⌉ ≥4 → N/7>3 → N>21 → N=22 |
| 68 (b). Minimum to guarantee 4 born same month. | k=12 → ⌈N/12⌉ ≥4 → N>36 → N=37 |
| 69 (a). Minimum to guarantee 3 last names begin with same first letter (26 letters). | k=26, want ⌈N/26⌉ ≥3 → N>52 → N=53 |
| 69 (b). Minimum to guarantee 3 born on same day of a 31‑day month. | k=31 → ⌈N/31⌉ ≥3 → N>62 → N=63 |
| 70. Tournament with n players, each wins at least once. Show at least two have same wins. | Possible wins 1 to n-1 (n-1 slots), n players → pigeonhole. |
| 71. 5 points in equilateral triangle of side 2 → two points distance <1. | Divide into 4 congruent small triangles (midpoints) → 5 points → one small triangle gets ≥2 points; its side =1, so distance <1. |
| 72. 7 distinct integers → two whose sum or difference is divisible by 10. | Consider remainders mod 10. There are 6 “pigeonhole‑pair” classes: {0}, {5}, {1,9}, {2,8}, {3,7}, {4,6}. 7 numbers → two fall in same class → sum or diff divisible by 10. |
📌 Exam tips for pigeonhole principle:
- Always identify the “holes” (categories, days, pairs, colours).
- For “minimum to guarantee” questions, think of the worst‑case scenario: distribute as evenly as possible, then add one.
- Generalised formula: if you want at least \(q\) in one hole, the minimum total = \(k(q-1) + 1\).
- Sometimes you need to cleverly partition the set into holes (e.g., pairs summing to 10).
- Draw small pictures if it helps – pigeons into holes is very visual!
🌟 You’re doing great! The pigeonhole principle appears in many exit exams. In the next chapter we’ll dive into recurrence relations. Keep learning! 🇪🇹