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?