Pigeonhole Principle

More pigeons than holes → some hole has two pigeons

ExistenceCountingCombinatorics

If $n+1$ objects are placed in $n$ categories, at least one category contains $\geq 2$ objects. Simple to state, but its applications are astonishing. Generalized: if $kn+1$ objects go in $n$ categories, some has $\geq k+1$.

When to use it

→When the statement says 'at least' or 'there exist'
→When you have more objects than categories
→When searching for a guaranteed existence
→In counting and combinatorics

How to think (step by step)

1Identify the 'pigeons': What are the objects?
2Identify the 'holes': What are the categories?
3Count: How many of each?
4Apply: If objects > categories, some category has 2+
5Conclude: This gives the required existence

Practice Problems

Three problems at increasing difficulty — try each before revealing the hint or solution.

📘Basic

In a room with

\(13\)

people, prove that at least

\(2\)

were born in the same month.

📙Intermediate

Choose

\(5\)

points inside an equilateral triangle with side length

\(1\)

. Prove at least two are within distance

\frac{1}{2}

of each other.

📕Advanced

Prove: among any

\(n+1\)

integers chosen from

\{1, 2, \ldots, 2n\}

, some two have the property that one divides the other.