The Pigeonhole Principle
What is the Pigeonhole Principle?
The pigeonhole principle says:
“If you try to place more objects than the number of containers, at least one container will get at least two objects.”
Or in simpler words:
“Too many items, too few boxes → something must share space.”
This idea looks almost too obvious…
yet it helps us prove surprisingly deep results in mathematics and in the Theory of Computation.
Why is it called the ‘pigeonhole’ principle?
Long ago, people used small compartments called pigeonholes to store documents and letters.
Each mail would go into one slot.
If you have:
- 7 letters
- 5 pigeonholes
Then at least one pigeonhole gets 2 or more letters.
It’s just unavoidable.
🌱 A Simple Diagram
Here’s a small visual to make the idea feel natural:
Pigeonholes (Boxes): P1 P2 P3
| | |
Objects (Pigeons): O1 O2 O3 O4
Try placing 4 objects into 3 boxes:
O1 → P1
O2 → P2
O3 → P3
O4 → ?? No empty box left!So O1, O2, O3 fit,
but O4 must share with some P1 / P2 / P3.
This is the principle in action.
🧠 Why is the pigeonhole principle useful in Theory of Computation?
Even though it sounds like a simple counting idea, it becomes a powerful proof tool.
You’ll often use it to show things like:
- Some strings must repeat.
- Some states in an automaton must be visited more than once.
- A machine cannot handle too many different inputs with too few states.
- A language cannot be recognized with limited memory.
Most importantly, it helps prove impossibility results.
🎒 Example (Automata Perspective)
Suppose you have a DFA with 5 states, and you run it on a string of 7 characters.
Each character moves the DFA from one state to another.
You now have a sequence of 8 state visits (including the starting state).
But there are only 5 states.
So at least one state must repeat.
This repeated state is the key idea behind the Pumping Lemma for regular languages.
All of this comes directly from the pigeonhole principle.
🧩 A Friendly Real-Life Example
Imagine you’re in a classroom with 31 students.
You ask everyone to tell you their birth month.
There are only 12 months.
Since 31 > 12:
➡️ At least three students must share the same birth month.
(Why three? Because 31 ÷ 12 is more than 2.)
Even if birthdays seem “random,”
the pigeonhole principle guarantees this.
🛠️ How We Use It in Proofs
A typical pigeonhole-based proof goes like this:
- Identify the objects.
These could be strings, states, numbers, or anything. - Identify the pigeonholes.
These are categories or containers. - Show that the number of objects > number of pigeonholes.
- Conclude:
At least one pigeonhole has 2 or more objects.
That’s all!
No calculations, no complex logic — just counting.
🌟 A Small Computation Example
Claim:
If a Turing machine has 20 states, and it processes an input of 30 steps,
then at least one state must repeat.
Reason (Pigeonhole Principle):
- Number of “pigeonholes” = 20 states.
- Number of “pigeons” = 31 state visits (start + 30 moves).
Since 31 > 20,
➡️ at least one state is visited more than once.
Author Profile
Latest entries
Equivalence of Regular Expressions and Regular LanguagesNovember 20, 2025Equivalence of Regular Expressions and Regular Languages
Regular ExpressionsNovember 20, 2025Regular Expressions — Theory of Computation
ITNovember 19, 2025Closure Under the Regular Operations — Theory of Computation
ITNovember 19, 2025Equivalence of DFAs and NFAs
About the Author
