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 states: if n+1 items are placed into n boxes, at least one box must contain two items. More generally, if m items are placed into n boxes with m > n, at least one box contains ⌈m/n⌉ items. This simple principle has powerful existence proofs in combinatorics and graph theory.
The pigeonhole principle sounds almost too obvious to be useful: if you have 13 socks in 12 drawers, at least one drawer holds 2 socks. The power comes from recognizing when a seemingly hard problem secretly has this structure hiding inside it. The art of applying the pigeonhole principle is identifying the right "pigeons" (objects being distributed) and the right "holes" (categories they fall into).
The basic form says: if n+1 objects are distributed among n categories, some category contains at least 2 objects. The generalized form sharpens this: if m objects go into n categories, at least one category contains at least ⌈m/n⌉ objects. This ceiling function is the key — it means the maximum must be *at least* the average, rounded up. If you have 25 students and 7 exam grades (A through F, plus one more), at least ⌈25/7⌉ = 4 students share a grade. This follows without knowing anything about who scored what.
The real skill is translating existence problems into this form. Consider: in any group of 13 people, must two of them share a birth month? Yes — there are 13 people (pigeons) and 12 months (holes), so by the basic form, at least two share a month. Notice that the principle guarantees *existence* without telling you *which* pair shares the month. This is an existence proof — it proves something must exist without constructing an example. This style of reasoning appears constantly in combinatorics and graph theory: if a graph has enough vertices relative to its structure, certain patterns must appear.
The most surprising applications come from cleverly defined categories. To prove that among any n+1 integers from {1, 2, ..., 2n}, two must be consecutive, partition {1,...,2n} into the n pairs {1,2}, {3,4}, ..., {2n-1, 2n}. These pairs are the holes; the chosen integers are the pigeons. Choosing n+1 integers forces two into the same pair, which are consecutive. The harder part is always inventing the right partition — once you have it, the principle does the rest automatically. Developing this skill means practicing on varied problems until you build a library of useful partition strategies.