Engines of Our Ingenuity

No. 2406
THE PIGEONHOLE PRINCIPLE

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.

top of a person's head, showcasing hair

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.

pigeons

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.

socks

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.

(Theme music)


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 Puzzlerís Pigeonhole. From the Web site of the Mathematical Association of America: http://www.maa.org/editorial/knot/pigeonhole.html. Accessed August 20, 2008.

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



The Engines of Our Ingenuity is Copyright © 1988-2008 by John H. Lienhard.