The Pigeonhole Principle

The pigeonhole principle, also known as Dirichlet's box principle, states that, given n boxes and m objects, where m is greater than n, at least one box must contain more than one object. It's a pretty straightforward concept, but it has a lot of applications in set theory and other areas.

I'll illustrate using a less serious application of the principle: Prove that there are at least two people in New York City with the same number of hairs on their heads.

Solution: There are around eight million people in New York City, since there are 8,000,000 people. Now, people can only have so many hairs on their heads. Since the average person has 100,000 hairs on their head, it seems highly unlikely that no-one has more than 1,000,000 hairs on their head. Then there would be only around 1,000,000 boxes to put the 8,000,000 people in. Therefore, some boxes will have to contain more than one object by the pigeonhole principles. Therefore at least two people in New York City have the same number of hairs.

If you think you're getting the hang of the pigeonhole principle (or if you think you need some more practice), there are some other problems on the pigeonhole principle problems page that you can try.