Combinatorics and discrete mathematics

The pigeonhole principle

If more objects are placed into boxes than there are boxes, some box must contain more than one.

IntuitionWhy must two pigeons share a hole?

Suppose you have $10$ pigeons and only $9$ pigeonholes, and every pigeon must fly into some hole. No matter how cleverly the pigeons are placed, at least one hole ends up with two or more pigeons in it — there simply are not enough holes for everyone to get their own. This obvious-sounding fact is called the pigeonhole principle, and despite its simplicity it proves surprisingly deep results across number theory, geometry and computer science.

A bipartite network connecting

10

pigeons to

9

holes: whichever way the edges are drawn, some hole vertex must receive at least two edges, since

10 > 9

SchoolStating the principle precisely

Definition: Pigeonhole principle

If $n$ objects are placed into $k$ boxes and $n > k$ , then at least one box contains at least $2$ objects. More generally, if $n$ objects are placed into $k$ boxes, some box contains at least $\lceil n/k\rceil$ objects.

n>k\ \Longrightarrow\ \exists\text{ box with}\ge2\text{ objects}

The number $\lceil n/k\rceil$ (" $n/k$ rounded up") is the smallest integer that is at least $n/k$ ; it is the guaranteed minimum load of the fullest box when $n$ objects are spread as evenly as possible over $k$ boxes. For example, splitting $n=10$ objects over $k=3$ boxes as evenly as possible gives loads $4,3,3$ , and indeed $\lceil 10/3\rceil=4$ .

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

How many objects, how many boxes, what is guaranteed
Objects $n$ / boxes $k$	Guaranteed minimum in the fullest box
$n=10,\ k=9$	$\lceil 10/9\rceil=2$
$n=13,\ k=12$	$\lceil 13/12\rceil=2$
$n=100,\ k=9$	$\lceil 100/9\rceil=12$
$n=k+1,\ k$ arbitrary	$\lceil (k+1)/k\rceil=2$

UndergraduateTwo theorems: the basic and the generalized principle

Theorem: The basic pigeonhole principle

If $n$ objects are distributed into $k$ boxes with $n>k$ , then at least one box contains at least $2$ objects.

Why is it true?

This is really a statement about counting, proved by assuming the opposite and reaching a contradiction: if every box had at most $1$ object, the boxes could not hold more than $k$ objects in total.

Proof

Assume, for contradiction, that the conclusion fails: every one of the $k$ boxes contains at most $1$ object.

Then the total number of objects distributed is at most $k\times1=k$ .

But we distributed $n$ objects, and $n>k$ by hypothesis, so the total number of objects distributed is $n>k$ .

These two counts of the same set of objects contradict each other ( $n>k$ but also total $\le k$ ), so the assumption was false: some box must contain at least $2$ objects.

Theorem: The generalized pigeonhole principle

If $n$ objects are distributed into $k$ boxes, then some box contains at least $\lceil n/k\rceil$ objects.

Why is it true?

The basic principle only guarantees $2$ objects somewhere; the generalized version sharpens this to the exact minimum forced by averaging $n$ objects over $k$ boxes, using the same contradiction idea but comparing against $\lceil n/k\rceil-1$ instead of $1$ .

Proof

Assume, for contradiction, that every box contains at most $\lceil n/k\rceil-1$ objects.

Then the total number of objects distributed is at most $k\left(\lceil n/k\rceil-1\right)$ .

Since $\lceil n/k\rceil$ is the smallest integer at least $n/k$ , we have $\lceil n/k\rceil-1<n/k$ , so $k\left(\lceil n/k\rceil-1\right)<k\cdot\frac{n}{k}=n$ .

So the total distributed is strictly less than $n$ , contradicting that all $n$ objects were distributed. Hence some box contains at least $\lceil n/k\rceil$ objects.

UndergraduateReal-world applications and worked examples

Despite its simplicity, the pigeonhole principle is a standard tool in computer science (proving that a hash table with more keys than slots must have a collision), in number theory (proving that some multiple of a given integer has a specific digit pattern), and in everyday combinatorics puzzles about scheduling, sorting and social networks.

Example: Socks in a drawer

A drawer contains socks of $4$ colors, with plenty of each color but mixed together in the dark. What is the smallest number of socks you must pull out to be certain of having a matching pair?

Solution

Think of the $4$ colors as $k=4$ boxes, and each sock you pull out as an object dropped into the box matching its color. A "matching pair" means some box receives at least $2$ objects.

By the basic pigeonhole principle, once you pull $n$ socks with $n>k=4$ , i.e. $n\ge5$ , some color box must contain at least $2$ socks — a matching pair is guaranteed.

Is $5$ actually the smallest such number? With only $4$ socks it is possible (though unlucky) to have pulled exactly one of each of the $4$ colors, with no pair yet. So $4$ socks do not guarantee a pair, but $5$ do.

The answer is $5$ socks.

Example: Two people at a party with the same number of friends

At a party of $n\ge2$ people, "friendship" is mutual and no one is a friend of themselves. Show that there must be two people at the party who have exactly the same number of friends present.

Solution

Each person's number of friends at the party is an integer between $0$ and $n-1$ (you cannot have more friends than the other $n-1$ people present), giving $n$ possible values and $n$ people — pigeonholing the friend-counts directly would only give $n$ boxes for $n$ people, not yet a forced collision.

The key extra observation is that the values $0$ and $n-1$ cannot both occur: if someone has $0$ friends, no one can have $n-1$ friends (which would mean being friends with everyone, including that person), and vice versa. So only $n-1$ distinct friend-counts are actually available: either $\{0,1,\dots,n-2\}$ or $\{1,2,\dots,n-1\}$ .

Now apply the basic pigeonhole principle with $n$ people (objects) and at most $n-1$ possible friend-counts (boxes). Since $n>n-1$ , some friend-count box must receive at least $2$ people.

Therefore at least two people at the party have exactly the same number of friends present.

If $13$ pigeons fly into $12$ holes, what does the basic pigeonhole principle guarantee?

Using the generalized pigeonhole principle, what is the guaranteed minimum number of objects in the fullest box when $n=100$ objects are placed into $k=9$ boxes?

Which everyday situation is a direct application of the pigeonhole principle?

In the party example where friendship is mutual, why can the friend-counts $0$ and $n-1$ not both occur among the $n$ guests?