A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
The pigeonhole principle: if n items go into m < n containers, some container has at least ⌈n/m⌉ items. This simple principle proves existence without constructive proof: often something must happen by counting alone.
Apply it to show that among any 13 people, two share a birth month. Generalized versions handle more complex scenarios. Practice translating real problems into pigeonhole form.
The principle guarantees existence but not uniqueness or constructibility. It's a proof technique, not a counting formula.
You already know the Pigeonhole Principle in its basic form: if you stuff n pigeons into m holes with n > m, at least one hole must contain more than one pigeon. What makes this principle powerful in practice is not the original statement — that's almost too obvious to be interesting — but the art of *identifying what the pigeons and holes are* in a given problem. That translation step is where the mathematical creativity lives.
The classic warm-up: among any 13 people, at least two must share a birth month. Here the "pigeons" are people and the "holes" are months (12 of them). With 13 people and only 12 months, the principle guarantees a collision. But the same structure shows up in far less obvious settings: among any 5 points placed inside a unit square, two must be within distance √2/2 of each other (divide the square into 4 smaller squares); among any sequence of n²+1 distinct real numbers, there must be either an increasing or decreasing subsequence of length n+1 (Erdős–Szekeres theorem). In each case, the proof doesn't construct the pair — it just shows by counting that they *must* exist.
The generalized pigeonhole principle sharpens the basic claim: if n items go into m containers, some container holds at least ⌈n/m⌉ items (the ceiling of n/m). With 100 students assigned to 12 months, at least one month has ⌈100/12⌉ = 9 students. This lets you make quantitative existence claims, not just qualitative ones. Many pigeonhole arguments in combinatorics and number theory use this to guarantee large repetitions or collisions within structured sets.
A key conceptual shift here: you have moved beyond *constructive* proofs, which show you exactly where the thing you're looking for is, into *existence* proofs, which show something must be there without telling you where. The pigeonhole principle is the simplest example of this style of argument. It proves existence by contradiction — assuming no hole has two pigeons leads immediately to a count contradiction. This non-constructive flavor recurs throughout discrete mathematics: Ramsey theory, the probabilistic method, and many results in combinatorics all prove things exist without building them explicitly.