Must Two People Here Share a Birthday Month?

With 12 people you can give everyone a month of their own: one each. With 13 you can’t, however you try. The widget lets you see why: once every month has one person, every month is “taken”, and the 13th person must go into a month that already has someone.

Now try the bigger groups in the widget, and fill in what you find.

People	12	13	24	25	40
The fullest month must hold at least	1	2	?	?	?

Here is the pattern. Divide the people by 12 and round up: 13 ÷ 12 is a little over 1, so at least 2; 25 ÷ 12 is a little over 2, so at least 3; 40 ÷ 12 = 3.33…, so at least 4. And the smallest group in which three must share a month is 2 × 12 + 1 = 25: one more than the most people you could fit with only two in each month.

An old desk in a post office has a grid of small open boxes, one for each street, where the letters are sorted. They are called pigeonholes, after the holes in the wall of a pigeon house. If there are more letters than pigeonholes, some pigeonhole gets at least two letters. That is the whole idea.

Why is it true? Suppose every box held at most one thing. Then k boxes would hold at most k things in all. But there are more than k. So some box must hold two. The general version is the same argument: if every box held fewer than n ÷ k things, all k boxes together would hold fewer than k × (n ÷ k) = n things. So some box holds at least n ÷ k, and since things come whole, at least n ÷ k rounded up: a box holding at least 3.33… people holds at least 4. Another way to say it is that the fullest box holds at least the average. If 40 people are shared among 12 months, the average month has 3.33… people, and you can’t have every month below average.

Notice what the principle does not say. It says some box gets two, not which box: Prakash knew two people share a month, but not which month, or who. And the boxes must cover every possibility, each thing in exactly one: everyone has a birthday in exactly one month, so the months work as boxes.

Now back to the hairs. A human head has about 100,000 hairs, 1 lakh, on average for black hair (about 1.5 lakh for blond hair, fewer for red). Nobody has anywhere near 1,000,000 (10 lakh). So take the boxes to be the possible numbers of hairs: 0, 1, 2, …, all the way to 1,000,000. That is 1,000,001 boxes. Each person in Kathmandu district goes in the box of their own number of hairs, bald people included (in box 0).

In the puzzles so far the boxes were handed to you: months, colors, hair counts. The art of the pigeonhole principle is in inventing the boxes. Once you have chosen them well, the proof is one line.

Five points in a square

Here is a square, 2 units on each side. Put five points anywhere inside it or on its edges. How far apart can you keep them? Try to make the closest two as far apart as possible.

You never get the closest two more than about 1.414 apart. Here is the proof. Cut the square into four small squares, each 1 unit on a side. Those are the boxes. Five points, four small squares: two points must be in the same small square (a point on a cut line can go in either). Two points in a square of side 1 are at most 1 apart across and at most 1 apart up and down, so by Pythagoras they are at most $\sqrt{1^2 + 1^2} = \sqrt 2 \approx 1.414$ apart, the length of its diagonal.

So among any five points in a square of side 2, some two are at most √2 apart. And √2 is the best that can be said: four points at the corners and one at the very middle are each at least √2 from the others. A proof that says “at most √2” and an example that reaches √2 together settle the question completely.

Ten numbers, two equal groups

This one was the very first problem of the 1972 International Mathematical Olympiad, held in Poland:

Take any ten different two-digit numbers. Show that you can always choose two groups of them, with no number in both groups, that have the same total.

Try it before reading the proof.

It looks hopeless to prove for every set of ten numbers. The pigeonhole principle does it in three lines, by counting.

• The things: the groups you can make from the ten numbers. Each number is either in a group or not, so there are 2 × 2 × … × 2 = 2¹⁰ = 1,024 choices, and leaving out the empty group, 1,023 groups.
• The boxes: the possible totals. The smallest a group’s total can be is 10 (one number, 10 itself). The largest is when all ten numbers are as big as possible: 90 + 91 + … + 99 = 945. So every total is one of the whole numbers from 10 to 945: at most 936 totals.
• 1,023 groups, at most 936 totals: two different groups have the same total.

One catch: those two groups might share some numbers. Take the shared numbers out of both: both totals drop by the same amount and stay equal, and now no number is in both. Neither group becomes empty, since one of two different groups with the same total can’t sit inside the other (it would have the smaller total).

Sometimes the boxes are hidden inside the puzzle, and the hard part is to see them at all.

Two people shook the same number of hands

At any gathering where people shake hands (nobody with themselves, nobody twice with the same person), however many hands each person shakes, there are always two people who shook the same number of hands. Try it with 4 people before reading on.

Here is why. Say there are 30 people. Each shook hands with some of the other 29, so each person’s count is one of 0, 1, 2, …, 29: thirty possible counts for thirty people. No luck yet: everyone could have a different count. But 0 and 29 can’t both happen. If somebody shook hands with all 29 others, then nobody shook no hands. So either the counts are all from 0 to 28, or all from 1 to 29. Either way, 30 people share only 29 possible counts, and two people must have the same.

Remainders as boxes

Remainders make perfect boxes, because there are only a few of them: dividing by 5 leaves 0, 1, 2, 3 or 4, five boxes.

Why every fraction’s decimal repeats

Divide 1 by 7 by long division. At each step you have a remainder, and the remainder decides everything that comes next. The remainders are 1, 3, 2, 6, 4, 5, and then 1 again, so the digits 142857 start over:

$$\frac{1}{7} = 0.142857\,142857\,142857\ldots$$

Is that luck? No. Dividing by 7, the only remainders other than 0 are 1 to 6: six boxes. So within seven steps a remainder must come back, and from then on the division repeats itself. (A remainder of 0 stops the decimal instead, as in 1/8 = 0.125.) So every fraction’s decimal either stops or repeats, with a repeating block shorter than the number you divide by: 1/17 repeats every 16 digits, 1/97 every 96.

The pigeonhole principle has limits, and they are worth knowing.

It only speaks when the numbers force it. 12 people can all have different months; only the 13th forces a pair. Below that line it says nothing, though chance says a lot: with only 5 people a shared month is already more likely than not (about 62 in 100, if every month were equally likely). That is the next topic’s surprise.

It needs things you can count to the end. Put endlessly many guests into endlessly many rooms and nobody need share: guest 1 in room 1, guest 2 in room 2, forever. A full hotel with endless rooms can even take more guests (the Grades 6–8 topic on Hilbert’s hotel, below).

• Will Two People in Your Class Share a Birthday? Pigeonholes say a shared birthday is certain with 367 people. Chance says it is likely with only 23.
• Are Some Infinities Bigger Than Others? What happens to “more things than boxes” when both are endless.
• How Did Bhaskara Solve Fermat’s Challenge 500 Years Early? The equation $x^2 - Ny^2 = 1$, which Dirichlet attacked with pigeonholes and Bhaskara solved with the chakravala.
• How Many Handshakes at a Party of 30? (Grades 6–8) Counting the handshakes themselves, the other half of this page’s handshake puzzle.
• Is There Room at a Full Hotel with Endless Rooms? (Grades 6–8) Where the pigeonhole principle stops working.
• Grade 10 Math: Sets Counting what is in two or three overlapping groups, the other basic tool of counting.
• Computing, Going Further (Grades 9–12): How Can a Message Use Fewer Bits? Compression, and why no program can shrink every file. (Coming soon.)