Two Londoners With the Same Number of Hairs
The puzzle
London has about 9 million inhabitants. A human head carries at most about 200,000 hairs.
Prove that at least two Londoners have exactly the same number of hairs on their heads. How large a group must share a count?
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
You do not have to find the two people. You only have to show they must exist.
Hint 2
There are more people than there are possible hair counts.
Show the answer Hide the answer
There are more people than possible counts, so at least two must match - and in fact at least 45 people share some count.
How to get there
Treat each possible hair count, 0 through 200,000, as a pigeonhole - about 200,001 of them - and each Londoner as a pigeon that goes into the hole matching their count.
With 9 million pigeons and 200,001 holes, some hole must contain more than one pigeon. That is the pigeonhole principle, and it settles the question without identifying a single person.
Pushing it further: if every hole held at most 44 people, the holes could account for only 44 x 200,001 = 8,800,044 people - fewer than 9 million. So some count is shared by at least 45. In general, n items in k boxes force some box to hold at least n/k rounded up: 9000000/200000 = 45.
The technique worth keeping
When a question asks whether two things must coincide, compare the number of things with the number of possible values. If items outnumber values, a collision is certain - and dividing gives the size of the largest forced group.