The Pigeonhole Principle

In one sentence

Put $n + 1$ objects into $n$ boxes, and some box holds at least two. More generally, put $mn + 1$ objects into $n$ boxes, and some box holds at least $m + 1$ .

The proof takes one line (by contradiction): if each box held at most $m$ , there would be at most $mn$ objects, not enough room. The real difficulty is that the problem never hands you the boxes. You have to partition the objects into classes so that “two in the same class” is exactly the property the problem wants. That is precisely the partition of a set from Vol. 1.

Example: any 11 numbers chosen from 1, 2, …, 20 include one that is a multiple of another

Step 1 / 4

First, try to avoid it
Take $11, 12, \dots, 20$ : twice any of them is more than $20$ , so none is a multiple of another. $10$ numbers can avoid it.
The wrong boxes
Box by odd part
The 11th number

Predict first

What is the largest number of numbers you can choose from $1, 2, \dots, 20$ so that none of them is a multiple of another?

Choose an answer first; then you can see the result.

Stop 1 · Families of subsets (Vol. 1)

Boxes do not have to hold numbers; they can hold subsets.

Example: among any 2ⁿ⁻¹ + 1 distinct subsets of {1, 2, …, n}, two are disjoint

Step 1 / 4

The objects are subsets
An $n$ -element set has $2^{n}$ subsets, and the problem takes $2^{n - 1} + 1$ of them: more than half.

$2^{n - 1} + 1$
Boxes: a subset and its complement
What sharing a box means
Conclusion and sharpness

Stop 2 · Periodic sequences (Vol. 5)

Infinitely many terms but only finitely many “states”: the pigeonhole principle forces a state to repeat, and the recurrence turns the repeat into a period.

Example: the remainders of the Fibonacci sequence mod m form a periodic sequence

Step 1 / 4

States
$F_{n + 1}$ is determined by the two terms before it, so take the remainders of two neighboring terms, $(F_{n} mod m, F_{n + 1} mod m)$ , as one state.

$(F_{n}, F_{n + 1}) mod m$
Boxes
From a repeat to a period
One example

Stop 3 · Existence problems (Vol. 5)

“Some run of consecutive terms must add up to a multiple of $n$ ”: the boxes hold not the numbers themselves but their prefix sums.

One problem, several solutions

Given any $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ , prove that some run of consecutive terms (at least one term) has a sum that is a multiple of $n$ .

Prefix sums into remainder boxes

Let $S_{k} = a_{1} + \dots + a_{k}$ ( $k = 1, \dots, n$ ). If some $S_{k} \equiv 0 (mod n)$ , we are done.

Otherwise the $n$ prefix sums fall into the $n - 1$ nonzero remainders, so $S_{i} \equiv S_{j}$ for some $i < j$ , and then $a_{i + 1} + \dots + a_{j} = S_{j} - S_{i}$ is a multiple of $n$ .

Example: $2, 6, 3, 7, 8$ ( $n = 5$ ). The prefix sums $2, 8, 11, 18, 26$ leave remainders $2, 3, 1, 3, 1$ ; $S_{2} \equiv S_{4}$ , so $3 + 7 = 10$ .

CostOne use of the pigeonhole principle, clean and quick.

Trying to construct it directly

For specific numbers you can find it by trial, but for $n$ general numbers no formula tells you which run it is.

That is the value of the pigeonhole principle: it proves the run exists without having to find it.

CostYou cannot say which run to take, only try them one by one: exactly the “existence only” proof the pigeonhole principle is good at.

Practice

Exercise 1Basic

What is the smallest number of lattice points (points whose coordinates are both integers) you must take in the plane to guarantee that the midpoint of some two of them is also a lattice point?

Exercise 2Basic

What is the smallest number of numbers you must choose from $1, 2, \dots, 100$ to guarantee that two of them are coprime?

Exercise 3Advanced

A family of subsets of ${1, 2, 3, 4, 5}$ has the property that any two of its subsets intersect. At most how many subsets can it contain?

Exercise 4Challenge

Given any $7$ distinct integers, prove that two of them have a sum or a difference that is a multiple of $10$ .

In one sentence

Example: any 11 numbers chosen from 1, 2, …, 20 include one that is a multiple of another

Stop 1 · Families of subsets (Vol. 1)

Example: among any 2ⁿ⁻¹ + 1 distinct subsets of {1, 2, …, n}, two are disjoint

Stop 2 · Periodic sequences (Vol. 5)

Example: the remainders of the Fibonacci sequence mod m form a periodic sequence

Stop 3 · Existence problems (Vol. 5)

Prefix sums into remainder boxes

Trying to construct it directly

Practice

Mistake Museum · Exhibits from this stop

The boxes are built, but sharing a box proves nothing

Showing “enough” but not “one fewer fails”

Stops on this line