Sometimes a proof can guarantee that an object exists without telling us which one it is. The pigeonhole principle does this by counting: if there are too many objects for every box to hold just one, some box must hold more. Its proofs also illustrate the difference between contraposition and contradiction.

The pigeonhole principle

Suppose we put five objects into four boxes, assigning each object to exactly one box. We cannot keep all five objects separate: at least one box contains at least two objects. It does not follow that every box contains two objects, or that the shared box contains exactly two.

The pigeonhole principle, often abbreviated PHP, makes the same claim for any positive integers $n$ and $m$:

If $n$ objects are distributed among $m$ boxes and $n>m$, then at least one box contains at least two objects.

The objects are the “pigeons,” and the boxes or categories are the “holes.” Every object must be assigned to exactly one hole. The hard part of an application is often choosing holes so that sharing one gives the conclusion we want.

Proof by contrapositive

Instead of assuming there are more objects than holes, assume that every hole contains fewer than two objects. We will show that there can be at most as many objects as holes.

Let $x_i$ be the number of objects in hole $i$, where $i=1,2,\ldots,m$. Each $x_i$ is a nonnegative integer, so “fewer than two” means $x_i\le1$. Counting all objects once gives

$$n=x_1+x_2+\cdots+x_m \le\underbrace{1+1+\cdots+1}_{m\text{ terms}} =m.$$

We have proved: if every hole contains at most one object, then $n\le m$. This is the contrapositive of the pigeonhole principle, so the original statement is true.

Seven points in a hexagon

Place seven points anywhere in a regular hexagon of side length $1$. Show that at least two of the points are at distance at most $1$ from each other.

The points are the pigeons. To choose useful holes, divide the hexagon into six equilateral triangles by joining its centre to its vertices. Each triangle also has side length $1$, and any two points in one of these triangles are at distance at most $1$.

Assign each point to a triangle containing it. A point on a shared edge or at the centre must be assigned to just one of the triangles that contains it; any fixed choice works. This avoids counting a point twice.

There are seven points and only six triangles. By PHP, one triangle contains at least two assigned points. Their distance is therefore at most $1$, as required.

This is a guarantee for every placement, not a probability statement. The non-strict bound also allows points on the boundary of the hexagon.

The generalized pigeonhole principle

If there are many more objects than holes, we can guarantee more than two in one hole. At least one hole must hold at least the average number of objects, rounded up to an integer.

For a real number $t$, the ceiling $\lceil t\rceil$ is the smallest integer greater than or equal to $t$. In particular,

$$\left\lceil\frac76\right\rceil=2.$$

The generalized pigeonhole principle says that distributing $n$ objects among $m$ holes, with $n$ and $m$ positive integers, guarantees at least one hole containing at least

$$\left\lceil\frac nm\right\rceil$$

objects. This is a lower bound, not an exact occupancy. The ordinary PHP follows whenever $n>m$, because then $n/m>1$ and its ceiling is at least $2$.

How many cards guarantee three of one suit?

Draw cards from a standard deck without jokers. What is the smallest number that guarantees at least three cards of the same suit?

The cards are the objects, and the four suits are the holes. If we draw $n$ cards, some suit appears at least $\lceil n/4\rceil$ times. We want

$$\left\lceil\frac n4\right\rceil\ge3.$$

The ceiling reaches $3$ as soon as the number inside it exceeds $2$; that number need not reach $3$ itself. Thus

$$\left\lceil\frac n4\right\rceil\ge3 \quad\Longleftrightarrow\quad \frac n4>2 \quad\Longleftrightarrow\quad n>8.$$

Since $n$ is an integer, nine cards suffice. They are also necessary for a guarantee: eight cards could consist of two from each suit, with no suit appearing three times. So the minimum is $9$.

Proof by contradiction

To prove a statement $P$ by contradiction, assume its negation $\neg P$ and derive something impossible. The assumption must then be false, so $P$ is true. In classical logic,

$$P\equiv(\neg P\Rightarrow\mathrm{False}).$$

The impossibility need not contradict an explicitly written hypothesis. For example, deriving $n<n$ is already enough: no number is strictly less than itself.

Proving the generalized pigeonhole principle

Let $x_i$ count the objects in hole $i$, for $i=1,2,\ldots,m$. Since every object is assigned to exactly one hole,

$$n=x_1+x_2+\cdots+x_m.$$

We want to prove that some hole contains at least $\lceil n/m\rceil$ objects. Suppose, for contradiction, that every hole contains fewer:

$$x_i<\left\lceil\frac nm\right\rceil \qquad\text{for every }i=1,2,\ldots,m.$$

To compare these counts with their average $n/m$, use the defining ceiling property:

$$\lceil t\rceil-1<t\le\lceil t\rceil.$$

If $t$ is an integer, the right-hand inequality is an equality; the left-hand inequality is still strict.

Each $x_i$ is an integer. Being below the integer $\lceil n/m\rceil$ therefore puts it at least one whole unit below:

$$x_i\le\left\lceil\frac nm\right\rceil-1<\frac nm.$$

Adding this strict inequality over all $m$ holes gives

$$n=x_1+x_2+\cdots+x_m <\underbrace{\frac nm+\frac nm+\cdots+\frac nm}_{m\text{ terms}} =m\frac nm=n.$$

This says $n<n$, a contradiction. The assumption that every hole falls below the bound is false. Hence

$$\exists i\in\{1,2,\ldots,m\}\quad x_i\ge\left\lceil\frac nm\right\rceil.$$

Notice the change from every in the assumption to some in the conclusion. Negating “every hole is below the bound” does not say that every hole reaches the bound.

Example: the square root of two is irrational

Write $\mathbb Z$ for the set of integers. A rational number can be written as $a/b$ for integers $a$ and $b$ with $b\ne0$. The set of rational numbers is denoted by $\mathbb Q$. An irrational number is a real number that is not rational. We want to prove

$$\sqrt2\notin\mathbb Q.$$

Any rational number can be written in lowest terms with a positive denominator: choose $b>0$ and $\gcd(a,b)=1$. Here $\gcd(a,b)$ is the greatest common divisor of $a$ and $b$; the condition says that they have no common positive divisor other than $1$.

Suppose, for contradiction, that $\sqrt2$ is rational. Choose such a reduced representation:

$$\sqrt2=\frac ab, \qquad a,b\in\mathbb Z,\quad b>0,\quad\gcd(a,b)=1.$$

Squaring both sides and multiplying by $b^2$ gives

$$2=\frac{a^2}{b^2} \quad\Longrightarrow\quad a^2=2b^2.$$

Thus $a^2$ is even. The parity result for integer squares says that an integer is even if and only if its square is even. Therefore $a$ is even, so $a=2k$ for some integer $k$.

Put this back into $a^2=2b^2$:

$$(2k)^2=2b^2 \quad\Longrightarrow\quad 4k^2=2b^2 \quad\Longrightarrow\quad b^2=2k^2.$$

Now $b^2$ is even, so the same parity result makes $b$ even. Write $b=2\ell$ for some integer $\ell$.

Both $a$ and $b$ have the common divisor $2$, contradicting $\gcd(a,b)=1$. Our assumption was false, so $\sqrt2$ is irrational.

Choosing lowest terms at the start is essential to this argument. Finding a common factor in an arbitrary fraction is not a contradiction; finding one in a fraction assumed to be reduced is.

Proof by cases

Sometimes different inputs need different arguments. A proof by cases splits the possibilities into conditions that cover every allowed input, then proves the desired conclusion in each case.

For $k$ cases, let $A_1,\ldots,A_k$ be the case conditions and $C$ the conclusion. The logical equivalence is

$$\bigl((A_1\lor\cdots\lor A_k)\Rightarrow C\bigr) \equiv \bigl((A_1\Rightarrow C)\land\cdots\land(A_k\Rightarrow C)\bigr).$$

To conclude $C$, we must also know that at least one case applies: $A_1\lor\cdots\lor A_k$. The cases must be exhaustive, meaning that they cover all possibilities. They may overlap; they do not have to be mutually exclusive. Choosing useful cases is part of the proof, even when the problem does not suggest them.

Example: an integer is no larger than its square

We want to prove

$$n\le n^2\qquad\text{for every }n\in\mathbb Z.$$

Let $n$ be an arbitrary integer. Split according to its sign.

Case 1: $n\le0$. A square is nonnegative, so

$$n\le0\le n^2.$$

Case 2: $n>0$. Because $n$ is an integer, $n\ge1$. Multiply $1\le n$ by the positive number $n$, which preserves the inequality:

$$n\cdot1\le n\cdot n, \qquad\text{so }n\le n^2.$$

Every integer satisfies either $n\le0$ or $n>0$, and both cases give the required result. This proves the claim.

The integer assumption matters exactly where we used $n>0$ to get $n\ge1$. It would not be valid for an arbitrary positive real number.