Math paradoxes

Glossary / Pigeonhole principle

Glossary · pigeonhole principle

Nobody counted, yet a match is certain?

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 wordspictures, analogies, small numbers

“In plain words” is hidden on all puzzles.

The hairs of Kyiv

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?

Try to avoid a match

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.

5

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.

Socks in the dark

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.

How many socks must you take to be sure of a matching pair?
And to be sure of a black pair?

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.

Rigoroustables, charts, formulas

“Rigorous” is hidden on all puzzles.

What the pigeonhole principle is

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

  • A guarantee, not a probabilityThe principle doesn't say "most likely". It says "always", for any arrangement, even the most cunning. That's why it's the tool for questions with "for sure" or "in the worst case".
  • The trick is choosing the boxesThe principle itself is obvious; all the cleverness lies in what to call the boxes: hair counts, colours, days of the year, outcomes of an experiment. Well-chosen boxes turn an incredible claim into a trivial one.
  • A proof of impossibilityIf there are more possible cases than distinct outcomes you can observe, two cases give the same outcome and you can't tell them apart. That's how you count the minimum number of weighings, tests or questions before you've even found a method.
  • It exists, but where is unknownThe principle proves that a match exists but doesn't show where. It won't help you find the two Kyiv residents with equal hair. Mathematicians call such proofs non-constructive.

Guarantee versus chance

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.

12

share of runs whose first match is at this itemguarantee: N = boxes + 1
Guarantee
On average the match comes at
Match before the guarantee

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.

Where the pigeonhole principle works

  • BirthdaysCounting 29 February, a year has 366 days, so among 367 people two are guaranteed to share a birthday. How many it takes for a match to be merely likely is a separate puzzle, and its answer surprises most people.
  • ArchiversNo lossless archiver can shrink every file. There are 256 files of 8 bits, but only 1 + 2 + 4 + … + 128 = 255 shorter strings, from the empty one to 7 bits. If every file got shorter, two different files would get the same archive, and you couldn't unpack both. So if an archiver shrinks some files, it must make others longer.
  • Hashes and passwordsThe SHA-256 hash function turns any file into a 256-bit number. There are infinitely many possible files and finitely many numbers, so different files with the same hash are guaranteed to exist. Yet nobody has found a single such pair for SHA-256: there are 2²⁵⁶ boxes. For the older 160-bit SHA-1, Google and the Dutch institute CWI showed such a pair in 2017.
  • How many tests you needEach test or weighing has a few possible results, and several checks give a finite number of different "histories". If there are more suspects than histories, two of them can't be told apart under any plan. That's how the puzzles about poisoned wine and a fake coin get a lower bound before anyone has found a solution.
Deepergeneralisations, theory, history

“Deeper” is hidden on all puzzles.

Two with the same number of friends

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.

Six guests and ten numbers

  • Three acquaintances or three strangersAmong any six people there are three who all know each other or three who are all strangers. Take one guest: each of the other five is someone they know or don't, so one of the two boxes holds at least three. If they know three, either two of those know each other (and with the guest that's three acquaintances) or all three are strangers to each other. If instead three are strangers to the guest, the same argument runs the other way round. With five people this fails: five at a round table who know only their neighbours give neither.
  • Ten numbers in any orderWrite 10 different numbers in any order. Among them there are always 4 that go up or 4 that go down (not necessarily next to each other). Paul Erdős and George Szekeres proved this in 1935; in general, n² + 1 numbers always contain n + 1 such. Nine numbers aren't enough: 7 8 9 4 5 6 1 2 3 has neither.

Where the name came from

  • Hair in 1622The oldest known statement was found by the historians Benoît Rittaud and Albrecht Heeffer (The Mathematical Intelligencer, 2014): the Jesuit Jean Leurechon's Latin book "Selectæ Propositiones" of 1622 says two people must have the same number of hairs or coins. So the hair example is two centuries older than the name itself.
  • Dirichlet's drawersThe principle is named after the German mathematician Peter Gustav Lejeune Dirichlet, who in 1834 called it the Schubfachprinzip, the "drawer principle", and used it in number theory, for instance to prove that any number can be well approximated by a fraction.
  • The pigeons are a mix-upThe English name comes from pigeonholes, the open compartments of a desk or cabinet for letters and papers. The pigeons in coops usually drawn next to the principle came later, once the word's original meaning had faded.

Where it shows up

More on “Games and logic”

All terms →