If you stuff \(n\) pigeons into \(k\) holes (as one often does), and if \(n \gt k\), then one of the holes must contain more than one pigeon.
It’s a simple enough idea, and obvious once written down, but still important to keep in mind as a formal truth. If a problem involves dividing things into categories, (e.g. putting points in regions of space, or assigning elements to subsets) or involves some sort of “collision” because to too many things, the pigeonhole principle might be key.
Examples
Putnam 2002 A2
Given any five points on a sphere,
show that some four of them
must lie on a closed hemisphere.
We’re putting points into hemispheres. The points are pigeons, and a pair of hemispheres will be the holes, but which hemispheres? …
Putnam 1978 A1
Let \(A\) be any set of \(20\) distinct integers
chosen from the arithmetic progression \(1,4,7,\dotsc,100.\)
Prove that there must be two distinct integers in \(A\) with sum \(104\).
How many pairs of numbers in that arithmetic progression sum to \(104\) anyways? (I.e. how many holes are there?)
There are six people at a party.
Every two people at the party
are either mutually good friends
or mutually total strangers;
there is no in-between, no acquaintances.
Prove that there must be at least one trio of people at the party
who are all mutually good friends with each other,
or are all mutually total strangers to each other.