Pigeonhole Principle: Simple Proofs Explained Step by Step

The pigeonhole principle says: if you put n+1 pigeons into n holes, at least one hole contains two or more pigeons. It sounds almost too obvious to be useful, yet it proves surprising facts across mathematics and computer science: you never need to know which hole is crowded, only that one must be.

Many existence proofs reduce to "more objects than categories": count the objects, count the boxes, and the principle hands you a guaranteed collision for free, with no construction and no search.

Key Concepts

• Basic form: placing n+1 items into n boxes forces some box to hold at least 2 items.
• Generalized form: placing N items into k boxes forces some box to hold at least ⌈N/k⌉ items (ceiling of N divided by k).
• Contrapositive view: if every box holds at most m items, there are at most m·k items in total.
• Pigeons and holes: "pigeons" are the objects you count; "holes" are the categories they fall into. Choosing the right categories is the creative step.

How It Works

Apply the principle in three steps:

1. Identify the objects (pigeons) and count them: N.
2. Identify the categories (holes) they must fall into and count them: k, with N > k.
3. Conclude some category holds at least two objects (or ⌈N/k⌉ in general). If every hole had at most one pigeon, there could be at most n pigeons, contradicting n+1.

Worked Example

Prove that among any 367 people, at least two share the same birthday (ignoring the year).

• Pigeons: the 367 people, so N = 367.
• Holes: the 366 possible birthdays in a leap year, so k = 366.
• Since 367 > 366, the basic pigeonhole principle applies directly: some birthday-hole contains at least two people.
• With the generalized form: ⌈367/366⌉ = 2, confirming at least two share a birthday.

Sharper: among 13 people, at least two share a birth month (⌈13/12⌉ = 2). The principle guarantees the shared month but not which one.

Common Misconceptions

• "The principle tells you which box is crowded." It does not. It guarantees existence only. Finding the actual crowded box needs extra work.
• "You need exactly n+1 objects." More objects only strengthen the conclusion via the generalized form. With 25 people and 12 months, ⌈25/12⌉ = 3 people share a birth month.
• "The holes must be equally likely." Probability plays no role. This is pure counting: 367 people and 366 days force a collision regardless of how birthdays are distributed.

Real-World Applications

• Hashing: with more possible inputs than hash values, collisions are unavoidable; hash tables are designed around handling them.
• Data compression: the pigeonhole principle proves no lossless compressor can shrink every possible file; some files must grow.
• Number theory: among n+1 integers there are two whose difference is divisible by n, proved by sorting remainders into n holes.

The pigeonhole principle turns "more pigeons than holes" into a guaranteed collision: n+1 objects in n boxes force a shared box, and N objects in k boxes force ⌈N/k⌉ in some box. Count the objects, count the categories, and the conclusion is free.