Pigeonhole Principle
Definition
The pigeonhole principle can be stated as follows:
If n + 1 objects are distributed among n containers, then at least one container must contain at least two objects.
A more general form is:
If N objects are distributed among k containers, then at least one container contains at least ⌈N/k⌉ objects, where ⌈x⌉ denotes the smallest integer greater than or equal to x.
Mathematical Form
Basic form
- If more objects than boxes exist, some box must contain at least two objects.
General form
- If objects are placed into boxes, then some box contains at least objects.
Why this is true
If every container had at most one object, then the total number of objects could not exceed the number of containers. Therefore, when objects exceed containers, repetition becomes unavoidable.
Main Content
1. Basic Pigeonhole Principle
- This is the simplest and most intuitive form of the principle.
- If you have more objects than containers, then at least one container must contain at least two objects.
Example
Suppose there are 13 students and only 12 months in a year. Then at least two students must have been born in the same month.
Here:
- Objects = 13 students
- Containers = 12 months
Since 13 > 12, one month must contain at least 2 students.
Another example
If 7 people shake hands with 5 possible hand categories, one category must occur at least twice. More generally, if items exceed categories, duplication is guaranteed.
Importance
This form is often used to prove that:
- two elements share a property,
- a duplicate exists,
- a repeated outcome must occur.
2. Generalized Pigeonhole Principle
- This version strengthens the basic idea by telling us how many objects must be in at least one container.
- If N objects are distributed into k containers, then at least one container contains at least ⌈N/k⌉ objects.
Example
If 100 balls are placed into 9 boxes, then at least one box contains at least:
So one box must contain at least 12 balls.
Why it works
If every box had at most 11 balls, then the maximum total would be:
But we have 100 balls, which is impossible. Therefore, at least one box must contain 12 or more balls.
Common use
This form is especially useful in:
- optimization arguments,
- proving lower bounds,
- counting problems,
- and existence proofs where “at least how many” is needed.
3. Applications in Set Theory, Relations, and Functions
- In set theory, the principle helps compare sizes of sets and identify unavoidable repetition.
- In functions, it is especially useful for proving that a function from a larger finite set to a smaller finite set cannot be injective (one-to-one).
Function example
Let where and . Since the domain has more elements than the codomain, by the pigeonhole principle, two different elements of must map to the same element in . Hence, cannot be one-to-one.
Relation example
If a relation groups elements into classes and the number of elements exceeds the number of classes, some class must contain multiple elements.
Set-theoretic use
If a set of objects is partitioned into finitely many subsets, the principle guarantees at least one subset has a certain minimum size.
Why it matters in theorem proving
It is often used in:
- proof by contradiction,
- existence proofs,
- proving non-injectivity,
- proving repetition in sequences,
- and proving that some structure must occur.
Working / Process
1. Identify the objects and containers
- Determine what the “objects” are and what the “pigeonholes” or categories are.
- Examples:
- students and months,
- numbers and remainders,
- elements and subsets,
- inputs and outputs of a function.
2. Compare quantities
- Count how many objects exist and how many containers are available.
- If objects > containers, the basic principle applies.
- If a stronger conclusion is needed, use the generalized form.
3. Apply the conclusion
- State that at least one container must contain multiple objects, or at least objects.
- Use this fact to prove the required result, often by contradiction.
Visual idea for understanding
If 5 objects are put into 3 boxes:
Objects: o o o o o
Boxes: [ ] [ ] [ ]
Distribution must force at least one box to have 2 or more objects.
A more detailed distribution could look like:
Box 1: o o
Box 2: o
Box 3: o o
This shows that repetition becomes unavoidable when objects exceed containers.
Advantages / Applications
- It provides a simple and powerful proof technique for showing that something must exist.
- It is widely used in combinatorics, number theory, set theory, and discrete mathematics.
- It helps prove properties of functions, especially showing that a mapping from a larger finite set to a smaller one cannot be injective.
- It is useful in real-world reasoning, such as assigning people to groups, finding shared birthdays, detecting repeated values, and analyzing hashing in computer science.
- It forms the basis of many classic results, such as:
- at least two people in a room sharing the same birthday month,
- two numbers having the same remainder modulo ,
- repeated symbols or patterns in sequences.
Summary
- The pigeonhole principle states that if more objects are placed into fewer containers, some container must hold more than one object.
- The generalized form tells us the minimum number that must be in at least one container: .
- It is a fundamental tool for proving existence, repetition, and non-injectivity in discrete mathematics.