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. Say 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.

Here are a few questions you may want to try out. Answers are on the answers page.

1. Five numbers are selected at random. Show that, of these five numbers, there exists three of them that sum to a multiple of three.
2. Five points are placed at random inside or on the edge of a unit square. Show that at least two points will be no more than

   1

   2

   .