Thursday, February 24, 2011

The Pigeonhole Principle

The Pigeonhole Principle states: If 10 pigeons are put into 9 pigeonholes, then at least one pigeonhole must contain 2 pigeons.

...Okay, I suppose it is not a very difficult principle. So let's use it in scenarios that are a bit harder to grasp right off the bat.

Your drawer contains 10 red socks and 10 black socks. You just woke up, barely got your eyes open, just reaching inside the drawer without looking. What is the fewest number of socks you need to take out to be sure to end up with a matching pair?
The answer is: three socks (← click to see). In this example there are 2 pigeonholes/sock colors (red and black) so with 3 pigeons/socks one of those must always contain a pair. Still with me?

Taking it up a notch then. Your drawer contains 2 red, 8 black, 10 blue and 16 white socks. Once again, what is the fewest number of socks you need to take out to be sure to end up with a matching pair?
Five socks. Think of the pigeons!

I guess that still makes sense. How about this: There must be at least two people living in Rome with the exact same number of hairs on their head. Even if the bald don't count. And that's not a probability either, that's a fact. How do we get to make such a claim?


The Pigeonhole Principle easily demonstrates it. Some web-searches will tell you that the average number of hairs on the human head is 100,000 to 150,000 hairs depending on color. Some estimates go up to 200,000 but that's it. But hey, let's use a ridiculous number of 1 million to be absolutely sure. Now, Italy's capital Rome has a population of about 2.8 million people. Yet there are only 1 million of possible “hair count configurations” those people can have. So there we have it. There are 2.8x more pigeons than there are pigeonholes, so there must be duplicates.

Here's another crazy one I found (on this site): On Thanksgiving, two or more of the consumed turkeys will have the same weight when rounded to the nearest millionth of a pound.
The site explains that the largest recorded turkey weighed 37 pounds. Taking that as the upper limit, that results in 37 million different options for the turkey weight when weighed to the millionth pound. With an estimated number of 46 million turkeys being eaten on Thanksgiving, you can once again apply the principle!

No comments:

Post a Comment