The pigeonhole principle is a simple counting idea with surprisingly powerful consequences. If more objects are placed into fewer containers, then at least one container must hold more than one object. This matters because it lets you prove that something must happen even when you cannot identify exactly where it happens.
It appears in number theory, combinatorics, computer science, and everyday reasoning about schedules, birthdays, and data storage.
The basic form says that placing n + 1 objects into n boxes forces at least one box to contain at least 2 objects. The generalized form says that if N objects are placed into k boxes, then some box contains at least ceiling(N/k) objects. To use the principle, you decide what counts as an object and what counts as a box, then compare the two counts.
Many elegant proofs come from choosing the boxes cleverly, such as remainders after division or possible sums.
Key Facts
- Simple form: If n + 1 objects are placed into n boxes, at least one box has at least 2 objects.
- Generalized form: If N objects are placed into k boxes, at least one box has at least ceiling(N/k) objects.
- Equivalent inequality: If every box has at most m objects, then k boxes can hold at most km objects.
- To force at least m + 1 objects in one box, you need more than km objects in k boxes.
- Remainder version: Among n + 1 integers, two have the same remainder when divided by n.
- Birthday example: Among 367 people, at least two share a birthday because there are only 366 possible birthdays including February 29.
Vocabulary
- Pigeonhole Principle
- A counting rule stating that if more objects are put into fewer boxes, at least one box must contain multiple objects.
- Object
- An item being assigned, such as a pigeon, person, number, card, or file.
- Box
- A category or container that objects are assigned to, such as a mailbox, birthday, remainder, or color.
- Ceiling Function
- The function ceiling(x) gives the smallest integer greater than or equal to x.
- Generalized Pigeonhole Principle
- A stronger form stating that when N objects are placed into k boxes, some box contains at least ceiling(N/k) objects.
Common Mistakes to Avoid
- Using the number of objects as the number of boxes, which hides the whole comparison. First identify the categories objects are assigned to, then count those categories separately.
- Forgetting to round up in the generalized form, which can give an impossible fractional answer. The maximum guaranteed number in one box is ceiling(N/k), not just N/k.
- Assuming the principle tells you which box is crowded, which it does not. It only proves that at least one such box must exist.
- Choosing boxes that are too detailed, which can make the principle fail to prove anything useful. A good choice of boxes groups objects by the property you want to force, such as same remainder or same birthday.
Practice Questions
- 1 A teacher has 29 students and 12 possible birth months. Use the pigeonhole principle to find the minimum number of students who must share a birth month.
- 2 How many socks must you pull from a drawer containing only 4 colors to guarantee that at least 3 socks are the same color?
- 3 Explain why among any 8 integers, two must have the same remainder when divided by 7, and state what that implies about the difference of those two integers.