Pigeons, socks and hairy cricketers

by Burkard Polster and Marty Ross

The Age, 7 September 2009

The alarm clock goes off on a dark morning and you stumble out of bed. You blindly grope in the wardrobe for your clothes: underwear, pants, T-shirt and, finally, socks.

Your socks are of various colours: black, a lighter shade of black, and pitch black. So, just randomly picking two socks out of the drawer, there is a fair chance of a horrible mismatch. On the other hand, grabbing the whole drawer would guarantee a matched pair. Being a mathematician, you long ago figured out that four is the minimum number of socks required to guarantee a match: one more than the number of colours.

Having solved your sock dilemma, it’s off to the bathroom for a quick combing. Gazing at your hair, it suddenly occurs to you that there must be “hairy twins” somewhere in Melbourne – there are two Melburnians with exactly the same number of hairs on their heads. Yes, this is pretty obvious for the bald guys. But it’s still true, even when considering only those with genuinely hairy heads.

Why is this so? From paying close attention to Warnie’s hair loss ads, you know that nobody has more than 200,000 hairs on their head. Now, quickly build some houses and label them from 1 to 200,000; then ask each Melburnian to count the hairs on their head and move into the corresponding house. Since there are more Melburnians than houses, there must be some house with at least two people in it. The people in that house have the same number of hairs. Quite Easily Done!

That was a fun distraction from your morning grooming, but now it’s time to leave for the mathematics conference. You are not sure which mathematicians will turn up, or how many. And some mathematicians are friends with each other, but not all. However, unless you end up there alone, you are sure that there will be at least two mathematicians attending who have exactly the same number of friends at the conference.

All the conclusions above are consequences of the very famous Pigeonhole Principle:

If the number of pigeons is greater than the number of pigeonholes containing them, then one of the pigeonholes must contain at least two pigeons.

The Pigeonhole Principle seems blindingly obvious, but there is something at least a little mysterious about it. Notice that although the principle promises a hole with two pigeons, it gives you no clue how to determine which hole that is. This is quite unlike more common mathematical scenarios, where the solution amounts to a precise formula.

Mysterious or otherwise, the Pigeonhole Principle is very powerful, and sometimes its application can be quite subtle. For example, it is not immediately obvious how to apply the principle to the question above, of the friendly conference of mathematicians. Here is another subtle application.

It turns out that 13 boy mathematicians and 13 girl mathematicians attend the conference. They sit together at a round table. Show that at least one person has girls for both their neighbours.

We’ll leave you to puzzle over that one, and we’ll happily respond to any suggested solutions.

www.qedcat.com