---
title: "State the pigeonhole principle"
subject: "Theory of Computation"
chapter: 1
key: "semester_3/theory_of_computation:pigeonhole-principle-state"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/pigeonhole-principle-state
site: BCT Engineering
---

# State the pigeonhole principle

Theory of Computation · Chapter 1: Introduction

- Asked in: 2073 Shrawan
- Video: [What Is the Pigeonhole Principle?](https://www.youtube.com/watch?v=B2A2pGrDG8I) — Spanning Tree
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/pigeonhole-principle-state
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-1

## Question

State the pigeonhole principle.

## Short answer

If more than n objects are placed into n boxes, at least one box contains two or more objects. In set terms, if |A| > |B|, no function from A to B is one-to-one. This principle underlies the pumping lemma for regular languages.

## Answer

**Statement.** If n + 1 or more objects (pigeons) are placed into n boxes (pigeonholes), then at least one box contains two or more objects.

**Set form.** If A and B are finite sets with |A| > |B|, then no function f : A → B is one-to-one; two different elements of A map to the same element of B.

**Generalized form.** If m objects are placed in n boxes, some box contains at least ⌈m/n⌉ objects.

**Proof (by contradiction).** Suppose every box has at most one object. Then the total number of objects is at most n, but we have n + 1 objects, a contradiction. So some box has two or more. ∎

**Examples**
- Among any 13 people, at least two were born in the same month (13 objects, 12 months).
- Among any 27 words in English, at least two begin with the same letter (26 letters).

**Use in automata.** In the pumping lemma, if a DFA has p states and reads a string of length ≥ p, the p + 1 states visited cannot all be different. Some state repeats, which gives a loop that can be pumped.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does the pigeonhole principle say?
   A. Every box holds exactly one object
   B. Placing n+1 objects in n boxes leaves one box empty
   C. Placing n+1 or more objects in n boxes puts at least two in some box
   D. Placing n objects in n boxes puts two in some box
   Answer: C. With more objects than boxes, some box has two or more. (Key point: Statement)

2. If m objects go into n boxes, some box has at least how many?
   A. m − n
   B. floor(m/n)
   C. m·n
   D. ceil(m/n)
   Answer: D. The average load is m/n, so some box gets at least its ceiling. (Key point: Generalized form)

3. Among 13 people, why do two share a birth month?
   A. 13 people and only 12 months
   B. Months have 30 days
   C. 12 people cannot share a month
   D. 13 is a prime number
   Answer: A. 13 objects in 12 boxes forces a repeat. (Key point: Example)

4. How is it used in the pumping lemma?
   A. A string of length ≥ p visits p+1 states, so one state repeats, giving a loop
   B. It shows every state is final
   C. It shows the string is accepted
   D. It shows a DFA has exactly p states
   Answer: A. The repeated state creates a loop that can be pumped. (Key point: Use in automata)