The pigeonhole principle is used to solve counting problems. \u00a0A simple example:<\/p>\n
In a ten day stretch, how many days must it rain to guarantee two consecutive days of rain?<\/em><\/p>\n The answer is six, and here’s why:<\/p>\n Step 1: \u00a0Organize the numbers from 1 to 10 into sets of two consecutive numbers:<\/p>\n {1,2}, {3,4}, {5,6}, {7,8}, {9,10}<\/p>\n Step 2: Imagine each number represents a day. \u00a0If 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). \u00a0However, when we pick the sixth one, we must return to one of the five pairs from which we’ve already drawn. \u00a0Therefore, we must pick the second number of a consecutive pair, guaranteeing two consecutive days of rain.<\/p>\n 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. \u00a0If we have six pigeons, but only five holes whence they came, two must come from the same hole.<\/p>\n The pigeonhole principle can be used to solve some surprising problems. \u00a0We’ll look at other examples in upcoming posts:)<\/p>\n Source: Grimaldi, Ralph. Discrete and Combinatorial Mathematics<\/em>.
\n Addison-Wesley,1994.<\/p>\n