title: "Pigeonhole Principle"

Pigeonhole Principle

Definition. The pigeonhole principle: if $n + 1$ or more objects are placed into $n$ boxes, some box receives at least two. Equivalently, there is no injective function from a finite set into a strictly smaller finite set.

Proved by induction plus contradiction in Lecture 2, Example 14. Its serious job arrives in Lecture 4: a machine with $n$ states reading a long string must repeat a state, and that repetition is the pump.