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.
About the Author
