Pigeonhole Principle — Mathematics Knowledge System

Overview

The pigeonhole principle states that if n items are placed into m containers, and n > m, then at least one container must hold more than one item. For example, of three gloves, at least two must be right-handed or at least two must be left-handed, since there are three objects but only two categories of handedness. This seemingly obvious observation, a type of counting argument, can be used to prove surprising results — for instance, since the population of London exceeds the maximum number of hairs a human head can have, there must be at least two Londoners with exactly the same number of hairs on their head.

Formal Definition

Definition

The basic (simple) form: if n objects are distributed into m boxes with n > m, some box contains at least 2 objects. The generalized form gives a stronger guarantee when n is much larger than m:

n > m \implies \exists \text{ a box with} \geq 2 \text{ objects}

Simple form

\left\lceil \frac{n}{m} \right\rceil = \left\lfloor \frac{n-1}{m} \right\rfloor + 1

Distributing n objects into m boxes guarantees some box contains at least this many objects

Generalized form

Worked Examples

There are 12 possible birth months (containers) and 13 people (items).
$n = 13, \; m = 12, \; n > m$
By the simple pigeonhole principle, some month must contain at least 2 people.
$\Rightarrow \exists \text{ month with} \geq 2 \text{ people}$

Answer: Yes — with 13 people and only 12 months, two people must share a birth month.

Practice Problems

Difficulty 3/10

A drawer has socks of 5 different colors. What is the minimum number of socks you must pull out (without looking) to guarantee a matching pair?

Difficulty 5/10

A hash function maps keys into 1000 buckets. If 1001 distinct keys are inserted, what does the pigeonhole principle guarantee?

Difficulty 4/10

In any group of 13 people, why must at least two share a birth MONTH?

Common Mistakes

Common Mistake

Believing the pigeonhole principle tells you WHICH box has extra items, or how many total collisions occur.

The principle only guarantees existence — that SOME box has at least 2 items (or ⌈n/m⌉ in the generalized form). It gives no information about which box or how many boxes exceed capacity.

Quiz

The pigeonhole principle states that if n items are placed in m boxes with n > m, then:

every box is fullat least one box contains more than one itemno box is emptythe items are evenly distributed

Why must a hash table handle collisions?

Hash functions are randomBy pigeonhole, more keys than buckets guarantees at least one shared bucketKeys are always duplicatedBuckets are unlimited

Summary

If n items are placed into m containers with n > m, at least one container holds more than one item.
The generalized form guarantees a box with at least ⌈n/m⌉ items.
It's a pure existence argument: it proves a collision must occur without identifying it.
Despite its simplicity, it proves non-obvious results, from birthday-coincidence puzzles to bounds in number theory and Ramsey theory.

References

WebsiteWikipedia — Pigeonhole principle