the pigeonhole principle
The pigeonhole principle is the most obvious idea in mathematics, dressed up: if you put more pigeons into fewer holes, at least one hole must hold two pigeons. With 13 people in a room, two must share a birth month, because there are only 12 months. It sounds trivial, yet it is astonishingly powerful precisely because it guarantees a collision without telling you where — you do not have to find the crowded hole, you just know it exists.
Stated plainly: if you place n items into m boxes and n > m, then some box must contain at least two items. A slightly stronger version says some box holds at least the ceiling of n/m items. The principle proves existence, not location: it tells you a repeat happens, never which one. To use it you set up the right pigeons and the right holes — the art is choosing what plays each role so that 'two pigeons in one hole' means something useful.
This is the secret engine of the pumping lemma. A DFA with n states, fed an input of length n or more, visits at least n+1 states along the way (counting the start). Treat the visited positions as pigeons and the n states as holes: some state must repeat. That repeated state creates a loop in the run, and any string that drives the machine around that loop can be repeated (pumped) any number of times while staying accepted — which is exactly the pumping lemma. The same counting shows that on any sufficiently long input a finite-memory machine must eventually re-enter a configuration it has seen before.
A DFA with 3 states reads the 4-symbol input aaaa. Its run visits 5 states q0, q1, q2, q3, q4 (start plus one per symbol). Five visits, only 3 distinct states — by pigeonhole two of them are the same state, so the run contains a loop that can be pumped.
More state-visits than states forces a repeat — the loop the pumping lemma exploits.
Pigeonhole guarantees that a collision exists, not where it is or which items collide. It is purely an existence argument; it never points you to the specific repeated hole.