The Art and Craft of Problem Solving

84 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS

3.3 The Pigeonhole Principle

Basic Pigeonhole

The pigeonhole principle,^3 in its simplest incarnation, states the following:

If you have more pigeons than pigeonholes , and you try to stuff the

pigeons into th e holes, then at least one hole must contain at least two

pigeons.

Amazingly, this trivial idea is revered by most mathematicians, for it is at least as

powerful as the Gaussian pairing trick. For example, the pigeonhole principle played

a crucial role in the solution of at least a third of the 1994 Putnam exam problems. A

few examples will convince you of its power.

Example 3.3. 1 Every point on the plane is colored either red or blue. Prove that no

matter how the coloring is done, there must exist two points, exactly a mile apart, that

are the same color.

Solution: Just messing around quickly yields a solution. Pick a point, any point.

Without loss of generality it is red. Draw a circle of radius one mile with this point as

center. If any point on the circumference of this circle is red, we are done. If all the

points are blue, we are still done, for we can find two points on the circumference that

are one mile apart (why?).

That wasn't hard, but that wasn't the pigeonhole solution. Consider this: just

imagine the vertices of an equilateral triangle with side length one mile. There are

three vertices, but only two colors available. The pigeonhole principle tells us that two

vertices must be the same color! _

Here is another simple example.

Example 3.3.2 Given a unit square, show that if five points are placed anywhere in­

side or on this square, then two of them must be at most V2/2 units apart.

Solution: Partition the unit square into four 1 x 1 squares. By pigeonhole, one

of these smaller squares must contain at least two points. Since the diagonal of each

small square is V2/2, that is the maximum distance between the two points. _

Quick and beautiful solutions are characteristic of pigeonhole problems. The

above example was quite simple. Solving most pigeonhole problems is often a three­

part process:

1. Recognize that the problem might require the pigeonhole principle.


2. Figure out what the pigeons will be and what the holes must be. This is fre­
   quently the crux move.

'The pigeonhole principle is sometimes also called the Dirichlet Principle in honor of the 19th-century

mathematician Peter Dirichlet.