Math: the pigeonhole principle

Tutoring math, you might see this topic from a university student.  The math tutor offers it as a point of interest.

The pigeonhole principle is used to solve counting problems.  A simple example:

In a ten day stretch, how many days must it rain to guarantee two consecutive days of rain?

The answer is six, and here’s why:

Step 1:  Organize the numbers from 1 to 10 into sets of two consecutive numbers:

{1,2}, {3,4}, {5,6}, {7,8}, {9,10}

Step 2: Imagine each number represents a day.  If we pick only five numbers, we can pick one from each set, potentially avoiding a consecutive pair (we can pick 1,3,5,7, and 9, for instance).  However, when we pick the sixth one, we must return to one of the five pairs from which we’ve already drawn.  Therefore, we must pick the second number of a consecutive pair, guaranteeing two consecutive days of rain.

Looking at the example above from the point of view of the pigeonhole principle, the pigeons are the numbers we pick, while the holes are the sets of consecutive pairs.  If we have six pigeons, but only five holes whence they came, two must come from the same hole.

The pigeonhole principle can be used to solve some surprising problems.  We’ll look at other examples in upcoming posts:)

Source: Grimaldi, Ralph. Discrete and Combinatorial Mathematics.
  Addison-Wesley,1994.

Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.

Leave a Reply