Mathematics
What is The pigeonhole principle?
The pigeonhole principle is a simple but powerful idea: if you have more items than containers, at least one container must hold more than one item. It sounds obvious, yet it proves surprising facts in math and computer science.
See it, don’t just read it.
Watch a 2-minute lesson with voice + animation that explains the pigeonhole principle.
Key things to understand
- 1If n+1 items go into n boxes, some box gets at least two.
- 2It's obvious to state but leads to non-obvious conclusions.
- 3Example: in any 13 people, at least two share a birth month.
- 4It's used to prove things must exist without finding them.
- 5It appears in computer science, like guaranteeing hash collisions.
Frequently asked questions
- What is a simple example of the pigeonhole principle?
- Among any 13 people, at least two must share a birth month, because there are only 12 months for 13 people.
- Why is the pigeonhole principle useful?
- It proves something must exist — like a repeat or a collision — without having to point to the specific case.
- Where is it used in computing?
- It shows that no method can compress every file, and that hash functions must sometimes map different inputs to the same output.