LOGIC & PUZZLES / COUNTING
The pigeonhole principle,
properly understood.
Counting can prove that a match exists without telling you where to find it.
THE MAIN IDEA
More objects than boxes forces a shared box.
The pigeonhole principle is a basic but surprisingly powerful statement: if you place more objects into fewer containers, at least one container receives multiple objects. The containers need not be literal pigeonholes. Group calendar dates by weekday, students by a chosen property, or numbers by their remainder after division. Suppose thirteen people are each assigned a birth month. There are only twelve months, so at least one month must be shared by two people. The claim guarantees a pair; it does not identify which month or say how many pairs exist. The stronger average form gives another useful bound. If n objects are distributed among k containers, some container holds at least the ceiling of n divided by k objects. With twenty-five objects in six boxes, at least one box contains five because four in each would hold only twenty-four. The argument relies on clearly specifying the boxes and the placement rule. “Objects” might be distinct people, while the property groups may overlap unless you define how each person is counted; overlapping categories can invalidate an apparently obvious pigeonhole setup. A proof should say why every object goes into exactly one of the chosen categories. Applications show up in computer science and everyday reasoning: duplicate birthdays must exist in a sufficiently large group, two records may share a hash value if the available hashes are fewer than the records, and repeated finite-state processes must eventually revisit a state. The theorem does not say that two items are identical in every way; they simply share whichever category was defined. Nor does it tell you which pair to inspect in a real dataset. For the birthday example, the number of people needed to guarantee a shared date is different from the number that makes a shared birthday likely. Probability asks how often outcomes occur under a model; pigeonhole counting establishes that some overlap is inevitable. That distinction is useful whenever a puzzle asks for a guarantee rather than a prediction. When stuck, count the available categories before studying individual arrangements. A small table can make the guarantee visible: if every box contained at most r objects, then at most r times k objects could fit, so any larger collection forces one box above r.
TRY THIS
Choose boxes that reveal something useful.
Take a group of objects and define four categories by their remainders when divided by four. Ask how many objects guarantee three sharing a category. Explain the maximum that would fit without a triple; write the bound rather than guessing at an arrangement.