Mathwords logoMathwords

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 AA and BB be finite sets with ∣A∣>∣B∣|A| > |B|. Then no function f:A→Bf: A \to B is injective. That is, there exist distinct a1,a2∈Aa_1, a_2 \in A with f(a1)=f(a2)f(a_1) = f(a_2). Generalized form: for any f:A→Bf: A \to B with ∣A∣=n|A| = n and ∣B∣=k≥1|B| = k \ge 1, some b∈Bb \in B satisfies ∣f−1(b)∣≥⌈n/k⌉|f^{-1}(b)| \ge \lceil n/k \rceil. Proof: suppose instead that every box held at most ⌈n/k⌉−1\lceil n/k \rceil - 1 objects. Since ⌈n/k⌉<n/k+1\lceil n/k \rceil < n/k + 1, the total would be at most k(⌈n/k⌉−1)<k⋅nk=nk(\lceil n/k \rceil - 1) < k \cdot \frac{n}{k} = n, which is a contradiction.

Key Formula

some box contains at least ⌈nk⌉ objects\text{some box contains at least } \left\lceil \frac{n}{k} \right\rceil \text{ objects}
Where:
  • nn = number of objects (pigeons)
  • kk = number of boxes (pigeonholes), with k ≥ 1
  • ⌈⋅⌉\lceil \cdot \rceil = ceiling function: round up to the nearest integer

Worked Example

Problem: Prove that if you choose any 5 distinct integers from {1,2,3,4,5,6,7,8}\{1, 2, 3, 4, 5, 6, 7, 8\}, 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.
{1,8}, {2,7}, {3,6}, {4,5},1+8=2+7=3+6=4+5=9\{1,8\},\ \{2,7\},\ \{3,6\},\ \{4,5\}, \qquad 1+8 = 2+7 = 3+6 = 4+5 = 9
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:
⌈54⌉=2\left\lceil \frac{5}{4} \right\rceil = 2
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 {1,2,3,4}\{1, 2, 3, 4\} have a largest pair sum of 3+4=73 + 4 = 7, 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 n/kn/k down, or concluding that every box gets ⌈n/k⌉\lceil n/k \rceil 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 ⌈13/12⌉=2\lceil 13/12 \rceil = 2 people, not 1. Other months may be empty. The principle also never tells you which box it is.

Related Terms