Pigeonhole Principle — Definition, Formula & Example
The pigeonhole principle is the fact that if you put more objects into boxes than there are boxes, at least one box must hold two or more objects. It is also called the Dirichlet box principle.
Let and be finite sets with . Then no function is injective. That is, there exist distinct with . Generalized form: for any with and , some satisfies . Proof: suppose instead that every box held at most objects. Since , the total would be at most , which is a contradiction.
Key Formula
Where:
- = number of objects (pigeons)
- = number of boxes (pigeonholes), with k ≥ 1
- = ceiling function: round up to the nearest integer
Worked Example
Problem: Prove that if you choose any 5 distinct integers from , two of them must add up to 9.
Step 1: Build the boxes. Split the 8 numbers into 4 pairs, each summing to 9. Every number belongs to exactly one pair.
Step 2: Place the pigeons. Put each of your 5 chosen numbers into the pair that contains it. You have 5 objects and 4 boxes, so some pair receives at least this many numbers:
Step 3: Conclude. A pair holds only two numbers, so that box contains both of them. They are distinct chosen numbers, and their sum is 9.
Answer: Any 5 distinct numbers from 1 to 8 must include two that sum to 9. Five is the smallest number of choices that forces this. The 4 numbers have a largest pair sum of , so no two of them sum to 9.
Why It Matters
In computer science, the principle proves that every hash function from a larger set of inputs to a smaller set of outputs must have collisions. It also proves that no lossless compression algorithm can shorten every file. In combinatorics and number theory courses, it drives existence proofs such as Dirichlet's approximation theorem. Those proofs show an object exists without ever constructing it.
Common Mistakes
Mistake: Rounding down, or concluding that every box gets objects.
Correction: Always round up, and remember that the principle only guarantees that at least one box reaches that count. For example, 13 people across 12 birth months guarantee that some month has people, not 1. Other months may be empty. The principle also never tells you which box it is.
