by Andrew Boyd

Today, pigeons and pigeonholes. The University of Houston's College of Engineering presents this series about the machines that make our civilization run, and the people whose ingenuity created them.

Here's a question. Do any two people in Houston have the same number of hairs on their heads? Sounds tough to answer. Lining people up. Counting their hair follicles. But there's actually an easy answer using something mathematicians call the pigeonhole principle.

The pigeonhole principle is a wonderful mathematical tool because it's so incredibly simple yet comes in so handy. It takes its name from the following example. Suppose we have ten pigeons but only nine pigeonholes to put them in. Since we have more pigeons than pigeonholes, at least one of the holes must have at least two pigeons in it. That's it. That's the pigeonhole principle. Whenever we have more items to put in holes than we have holes, at least one hole must contain more than one item.

The pigeonhole principle isn't a great mathematical truth. It's just an observation — and a pretty obvious one. But that's why mathematicians take pleasure in using it. It's so basic that when it shows up in the solution of a more difficult problem it evokes a smile. How could the pigeonhole principle be used to solve anything but the most trivial problems? But with a little ingenuity, it can. Let's take another look at our hair problem. The average head has 150 thousand hair follicles. So we can safely assume there's no head with more than, say, a million hairs on it.

Now let's imagine we have a collection of holes labeled zero through a million. We'll take all the residents of Houston and put them in the holes corresponding to the number of hairs on their heads. But Houston has a population of over two million. So by the pigeonhole principle, at least one hole (and probably many) will contain at least two people. We can be certain that at least two people in Houston have the same number of hairs on their heads. And we haven't counted anything.

The fascinating thing about the pigeonhole principle is that it's the solution to many questions that, at least at first glance, seem difficult to answer. The tricky part is recognizing that the pigeonhole principle can be used, and then figuring out what are the pigeons and what are the holes. For example, suppose we're in a room full of people who spend the start of a meeting shaking hands with their friends and acquaintances. Each person may shake a lot of hands or just a few. But when the handshaking's done, at least two people are guaranteed to have shaken exactly the same number of hands. Think about it. It's a consequence of the pigeonhole principle.

Do you have three different styles of socks mixed up in your dresser? No worries. Just pull out any four socks and you're sure to have a matching pair. Once again, it's the pigeonhole principle at work.

Of course, many more challenging problems can be solved with the pigeonhole principle. You can find links to some on the Engines web site. Pigeons and pigeonholes. Who'd have ever thought we could find such a great use for them?

I'm Andy Boyd at the University of Houston, where we're interested in the way inventive minds work.

Notes and References:

A number of fun exercises using the pigeonhole principle can be found at the following links.

Pigeonhole Principle. http://www.cut-the-knot.org/do_you_know/pigeon.shtml. Accessed August 20, 2008.

The photo of the pigeons in pigeonholes is courtesy of Wikipedia. All other photos are by E. A. Boyd.