Put more objects into boxes than there are boxes, and at least one box holds more than one object. It is the kind of statement that feels too obvious to be worth naming, and it has a name, a date and a long record of results that depend on it.
More than you would expect. first stated it in 1834, and in its general form, placing objects into boxes guarantees at least one box with at least the of the ratio between them. MathWorld notes its important applications in , where the principle does work no calculation can.
The statement is plain: given boxes and objects, with more objects than boxes, at least one box must contain more than one object. Nothing about it requires calculation, and that is the point.
It has a history. Dirichlet first stated it in 1834, and the name Dirichlet’s box principle is still the one a reference work files it under, with the pigeonhole principle as the familiar alias.
The general form is sharper than the simple one. If objects are placed into boxes, then there exists at least one box containing at least the ceiling of objects divided by boxes, so with ten objects in three boxes some box holds four.
What it buys is . MathWorld notes important applications in number theory, and the argument always has the same shape. Count the possible values, count the candidates, and if the candidates outnumber the values then two coincide.
wat. Thirteen people in a room guarantee two born in the same month, and nobody has to be identified.
wat wat
It proves that something exists without producing it, which is a kind of argument worth recognizing when you meet it.
How do we know?
The statement, its general form with the ceiling function, the attribution to Dirichlet and the date are given in the Wolfram MathWorld entry for Dirichlet’s box principle.
What is still unknown
The principle says a box with repeats exists and never says which one, so it cannot be used to find the thing it proves.
Learn something?
Where to next
How many guests do you need before three of them must all know each other?combinatorics
Did Alan Turing really prove the halting problem attributed to him?proof
Why is there always one point in the coffee that did not move?proof