The pigeonhole principle (Dirichlet)

What just happened?

We placed N objects into M boxes, spreading them as evenly as possible. When there are more objects than boxes, at least one box must take a second object — there is no other way.

Dirichlet’s pigeonhole principle:

If we place N objects into M boxes and $N > M$, then at least one box contains two or more objects. N — number of objects, M — number of boxes.

General version (stronger):

Not just “at least two” — there is always a box with at least the ceiling of the average:

For 13 people and 12 months: $\lceil 13/12\rceil = 2$ — a guaranteed pair. For 25 people and 12 months: $\lceil 25/12\rceil = 3$ — a guaranteed triple.

Why does this work?

Proof by contradiction: if every one of the M boxes had at most one object, then at most M objects would fit in total. But we have N > M, so that is impossible — a contradiction. The collision is therefore necessary.

Why you need this for the exam:

The pigeonhole principle is a flagship tool in combinatorial proofs. The trick: name the “objects” and “boxes” so that there are N and M of them with N > M — the rest follows on its own. Classics: two people with the same number of acquaintances, two points close together, a repeated remainder of a division.

Remember: more objects than boxes ⇒ a certain collision. In general the fullest box has at least ⌈N/M⌉ objects. It is not chance — it is necessity.