6.3 The Pigeonhole Principle

Section 6.2 counted how many arrangements or selections are possible. The pigeonhole principle answers a different question: when are repeated assignments unavoidable, regardless of how cleverly objects are arranged?

Its strength comes from needing very little information. We often do not need to know which collision occurs—only that some collision must occur.

The basic pigeonhole principle

If more than $k$ objects are placed into $k$ boxes, then at least one box contains at least two objects.

The traditional names are:

• objects are pigeons;

• boxes are pigeonholes.

The objects and boxes can represent anything.

Proof by contradiction

Assume no box contains two objects. Then every one of the $k$ boxes contains at most one object, so all boxes together contain at most

objects.

But the premise says there are more than $k$ objects. This is a contradiction. Therefore some box contains at least two.

This proof shows why the inequality must be strict. Placing exactly $k$ objects into $k$ boxes can put one object in each box with no collision.

Modeling is the main challenge

To apply the principle, identify:

1. the objects being assigned;

2. the boxes representing possible categories;

3. why every object belongs to exactly one box;

4. why the number of objects exceeds the number of boxes.

Example: birth months

Among $13$ people, at least two were born in the same month.

• pigeons: the $13$ people;

• pigeonholes: the $12$ months;

• assignment: each person goes to their birth month.

Because

a shared month is guaranteed.

The principle does not tell us which month or which pair of people. It proves existence.

Example: remainders

Choose $6$ integers. When divided by $5$, each integer has one remainder among

There are $6$ integers and $5$ remainder classes, so two chosen integers have the same remainder modulo $5$.

If the two integers are $a,b$, then

This connects the pigeonhole principle to the equivalence classes from Section 4.3.

A function interpretation

Assigning objects to boxes defines a function

where $P$ is the pigeon set and $H$ is the hole set.

If

then $f$ cannot be injective. Therefore there exist distinct pigeons $p_1,p_2$ with

The “collision” is exactly a failure of injectivity.

Common mistakes

The pigeonhole principle is simple, but its model can fail.

• Using categories that overlap means an object may not have a unique box.

• Forgetting a possible category makes the hole count too small.

• Having equal numbers of pigeons and holes does not force a collision.

• The conclusion guarantees at least one crowded box, not that every box is crowded.

For example, $13$ people and $12$ months guarantee a shared month, but they do not guarantee that every month contains a birthday.

Launch tokens into category portals while an adversary tries to avoid all collisions. You choose the number of holes and placement strategy; the arcade identifies the exact launch at which injectivity becomes impossible and produces the colliding witness pair.

The generalized pigeonhole principle

The basic principle guarantees a box with at least $2$ objects. With more objects, we can guarantee a larger load.

If $N$ objects are placed into $k$ boxes, then some box contains at least

objects.

The symbol $\lceil x\rceil$ is the ceiling of $x$: the smallest integer greater than or equal to $x$.

For example,

So placing $17$ objects into $5$ boxes guarantees that some box contains at least $4$ objects.

Why the ceiling bound is unavoidable

Let

Suppose every box contained at most $q-1$ objects. Then all $k$ boxes together would contain at most

objects.

Because $q-1<N/k$, we have

contradicting the fact that all $N$ objects were placed. Therefore at least one box contains $q$ objects.

Balanced distribution shows the guarantee is tight

Write

Then we can distribute:

• $q+1$ objects into $r$ boxes;

• $q$ objects into the remaining $k-r$ boxes.

The largest load is

So the guarantee cannot generally be improved.

For $N=17,k=5$:

A most-balanced distribution has loads

At least one box must reach $4$, and this arrangement shows that no box must necessarily reach $5$.

Solving reverse guarantee questions

To guarantee at least $r$ objects in one of $k$ boxes, ask how many objects can be placed while keeping every box at most $r-1$.

That maximum is

One more object forces the desired load:

Example: guaranteeing four matching colors

Socks come in $5$ colors. How many socks must be selected to guarantee $4$ of one color?

At most $3$ socks of each color can be selected without reaching $4$, for a total of

The next sock forces some color to have $4$:

Applications to data and algorithms

The generalized principle appears whenever finite resources receive many items:

• hashing keys into table buckets;

• distributing requests among servers;

• assigning students to time slots;

• grouping integers by remainder;

• storing files in fixed categories.

It provides a lower bound on the best possible maximum load. Even a perfect load-balancing algorithm cannot distribute $N$ jobs among $k$ servers with every load below $\lceil N/k\rceil$.

Act as a scheduler trying to minimize the busiest server while jobs arrive. An adversary changes the arrival count and number of servers; live lower bounds compare your distribution with the optimal balanced pattern and expose exactly when a requested maximum load is impossible.

Section bridge

The pigeonhole principle reasons from total counts to forced local behavior. The final section returns to exact counts for overlapping sets and repeated algebraic choices. Binomial coefficients will organize expansions, while inclusion–exclusion will repair the overlap problem left open in Section 6.1.