State the pigeonhole principle

Statement. If n + 1 or more objects (pigeons) are placed into n boxes (pigeonholes), then at least one box contains two or more objects.

Set form. If A and B are finite sets with |A| > |B|, then no function f : A → B is one-to-one; two different elements of A map to the same element of B.

Generalized form. If m objects are placed in n boxes, some box contains at least ⌈m/n⌉ objects.

Proof (by contradiction). Suppose every box has at most one object. Then the total number of objects is at most n, but we have n + 1 objects, a contradiction. So some box has two or more. ∎

Examples

• Among any 13 people, at least two were born in the same month (13 objects, 12 months).
• Among any 27 words in English, at least two begin with the same letter (26 letters).

Use in automata. In the pumping lemma, if a DFA has p states and reads a string of length ≥ p, the p + 1 states visited cannot all be different. Some state repeats, which gives a loop that can be pumped.