the pigeonhole principle

If you put 13 pigeons into 12 pigeonholes, at least one hole must contain two or more pigeons — there simply are not enough holes. That obvious-sounding statement is the pigeonhole principle, and despite its simplicity it proves surprising existence facts. It does not tell you WHICH hole is crowded, only that one must be; it is a tool for showing that something must exist, not for finding it.

The basic form: if you place n items into m containers and n is greater than m, then at least one container holds at least two items. The generalised form sharpens this: if you place n items into m containers, some container holds at least the ceiling of n/m items (round up). For example, among any 100 people, since there are at most 99 possible distinct integer ages from 0 to 99 if we cap there — actually the cleaner classic is: among any 13 people, at least two share a birth month, because there are only 12 months and 13 is more than 12. The art is choosing what the 'pigeons' and 'holes' should be so that the principle bites.

Pigeonhole is purely an EXISTENCE tool — it guarantees a collision or a repeat without constructing it, which is why it feels like getting something for nothing. It underlies many counting and probability arguments: it instantly proves that in any group of 367 people at least two share a birthday (only 366 possible dates), and it is the rigorous backbone behind 'why a perfect hash with more keys than slots must collide'. The honest limit: it tells you a coincidence is unavoidable, never how to locate it or how likely a near-coincidence is (that softer question is the birthday problem).