Skip to content
Know.itKnow.it
Create an animated lesson
On request

This article is free to read. Creating a lesson uses your daily or stored credits; review the language and settings before starting.

What is the pigeonhole principle?

MathematicsLesson on requestFree to read

Quick answer

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. If n+1 items go into n boxes, some box gets at least two.

Key things to understand

  1. If n+1 items go into n boxes, some box gets at least two.
  2. It's obvious to state but leads to non-obvious conclusions.
  3. Example: in any 13 people, at least two share a birth month.
  4. It's used to prove things must exist without finding them.
  5. It appears in computer science, like guaranteeing hash collisions.

People also ask

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.