Glossary / Pigeonhole principle
Usually, to say anything for sure about millions of people, you have to count them, or at least survey a sample, and then "for sure" turns into "most likely". The pigeonhole principle gives a real guarantee without counting anything: if there are more items than boxes, some box ends up with at least two. It sounds like a trifle every child knows. Yet from this trifle come claims that look impossible: about the hair of Kyiv's residents, socks in the dark and files no archiver can shrink.
“In plain words” is hidden on all puzzles.
Kyiv has about three million residents. A human head usually has 100–150 thousand hairs, some more, some fewer, and a bald one has none. Nobody is going to count them.
Without counting a single hair, can you claim that Kyiv has two people with exactly the same number of hairs on their heads?
It's guaranteed. More than that: at least three Kyiv residents have the same number of hairs.
Be very generous: nobody has a million hairs. Then there are exactly a million possible numbers, from 0 to 999,999. Picture a million boxes labelled with those numbers, and every Kyiv resident steps into their own. If each box held at most two people, the boxes could take only 2,000,000. But Kyiv has 2,952,301 residents (the city statistics estimate for 1 January 2022). So at least one box holds at least three. Who those people are and how many hairs they have, the principle doesn't say. It only says they exist.
Here are some boxes and one item more than there are boxes. Drop the items one by one by tapping a box, and try to keep any two from ending up together. You control every step, and no chance gets in your way.
The cleverest strategy only postpones the match until the last item; it can't cancel it. Try the "drop at random" button as well: when items fall at random, two usually share a box much sooner. A guarantee and a chance are different things, and below we compare them.
A drawer holds 10 black and 10 white socks, all mixed up. The light is off and they feel the same. You pull socks out by touch without putting any back.
Both answers come from the same move: picture the unluckiest draw and count how many socks it can "eat" without a pair. The boxes here are the colours. With two colours, two of any three socks must match. For a black pair there's only one box that counts, and the worst case first hands you all ten white ones.
“Rigorous” is hidden on all puzzles.
The pigeonhole principle: if N items are put into k boxes and N is greater than k, some box gets at least two items. More generally, some box gets at least ⌈N/k⌉ items, that is N/k rounded up. The proof takes one line: if every box held fewer, there would be fewer than N items in all.
⌈2,952,301 / 1,000,000⌉ = ⌈2.95…⌉ = 3 Kyiv residents with equal hair counts · ⌈3 / 2⌉ = 2 socks of one colour out of three · ⌈13 / 12⌉ = 2 people with one birth month out of thirteen
The pigeonhole principle tells you when a match becomes unavoidable. But when items fall at random, a match usually comes sooner. Take 12 boxes, the months of the year. Among 13 people two are guaranteed to share a birth month. But at which person does a shared month actually appear if people are picked at random? The simulation drops items into random boxes until two land together, and repeats this 10,000 times.
The gap between the bars and the dashed line is the gap between two questions. "How many do you need for a match to be unavoidable?" is answered by the pigeonhole principle, and the answer is always boxes plus one. "How many do you need for a match to be likely?" is a question for probability theory, and its answer is much smaller, because the number of pairs that could match grows very fast.
“Deeper” is hidden on all puzzles.
In any group of two or more people there are two who have the same number of friends within the group. It holds for any group: a school class, a department, wedding guests. The boxes are the possible numbers of friends. In a group of n people each can be friends with 0, 1, …, n − 1 others: n boxes for n people, so it seems there might be no match. But the boxes 0 and n − 1 can't both be occupied: if someone is friends with everyone, nobody has zero friends. So there are really n − 1 boxes for n people.
An option that gives a player more than any other option of theirs, whatever the others choose.
A discount pays a coffee shop whatever the shop next door does, yet when both cut, each earns three times less than if both had kept their price.
A set of strategies where nobody gains by changing their own while the others keep theirs.
In the prisoner's dilemma both betray, though both would be better off silent: an equilibrium is not the best outcome.
Solving a game from the end: the last move first, then the one before it, back to the first.
In the centipede game logic says grab the pennies on the very first move, though playing on would give both of them hundreds, and real people almost never do it.
Everyone knows a fact, everyone knows that everyone knows, and so on without end.
Two generals can swap a thousand confirmations and still lack common knowledge, so neither dares to attack first.
A quantity no allowed move can change: if it differs between the start and the goal, the goal can't be reached.
Cut two opposite corners off a chessboard, and 31 dominoes can no longer cover the 62 squares, however you lay them.