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:

1. Identify the objects.
   These could be strings, states, numbers, or anything.
2. Identify the pigeonholes.
   These are categories or containers.
3. Show that the number of objects > number of pigeonholes.
4. 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

examhopeinfo@gmail.com

Administrator

Visit Website View All Posts