The pigeonhole principle, also known as Dirichlet’s box principle states that, given two natural numbers n and m with n > m, if n items are put into m pigeonholes, then at least one pigeonhole must contain more than one item. Another way of stating this would be that m holes can hold at most m objects with one object to a hole; adding another object will force one to reuse one of the holes, provided that m is finite.
The pigeonhole principle is an example of a counting argument, which can be applied to many formal problems, including ones involving infinite sets that cannot be put into one-to-one correspondence.
An easy example of the pigeonhole principle involves the situation when there are five people who want to play softball (n = 5 objects), but there are only four softball teams (m = 4 holes). This would not be a problem except that each of the five refuses to play on a team with any of the other four. To prove that there is no way for all five people to play softball, the pigeonhole principle says that it is impossible to divide five people among four teams without putting two of the people on the same team. Since they refuse to play on the same team, at most four of the people will be able to play.
The following is another example of the pigeonhole principle:
Assume that in a box there are 10 black socks and 12 blue socks and you need to get one pair of socks of the same color. Supposing you can take socks out of the box only once and only without looking, what is the minimum number of socks you’d have to pull out at the same time in order to guarantee a pair of the same color?
The correct answer is three. To have at least one pair of the same color (m = 2 holes, one per color), using one pigeonhole per color, you need only three socks (n = 3 objects). In this example, if the first and second sock drawn are not of the same color, the very next sock drawn would complete at least one same-color pair (m = 2).
The pigeonhole principle may be used to demonstrate possibly unexpected results. For example, there must be at least two people in London with the same number of hairs on their heads. A typical head of hair has around 150,000 hairs; it is reasonable to assume that no one has more than 1,000,000 hairs on his head (m = 1 million holes). There are more than 1,000,000 people in London (n is bigger than 1 million objects). If we assign a pigeonhole for each number of hairs on a head, and assign people to the pigeonhole with their number of hairs on it, there must be at least two people with the same number of hairs on their heads.
Here’s how someone would mathematically solve a pigeonhole problem:
Suppose a musical group has 11 weeks to prepare for opening night, and they intend to have at least one rehearsal each day. However, they decide not to schedule more than 12 rehearsals in any 7-day period to keep from getting burned out. Prove that there exists a sequence of successive days during which the band has exactly 21 rehearsals.
This problem can be solved by a double application of the pigeonhole principle.
First, since the band has no more than 12 rehearsals per week, they can’t have more than 132 rehearsals in 11 weeks. (To see this, let x_k denote the number of games played in each of the 11 consecutive weeks, and note that they cannot sum to greater than 132 if they are each no greater than 12.)
Now let x_n denote the total number of rehearsals that have been held after n days. Since the band rehearses at least once per day, we have
1 <= x_1 < x_2 < x_3 < … < x_77 <= 132
Also, we can add 21 to each of these numbers to give the sequence
(x_1 + 21) < (x_2 + 21) < … < (x_77 + 21) <= 153
There are 77 numbers x_n and 77 more numbers x_n + 21 for a total of 154 numbers, all in the range from 1 to 153. Thus, at least two of these 154 numbers must be equal. But the x_n are all distinct, as are the (x_n + 21), so any “overlap” must be between a number of the form x_n and one of the form (x_m + 21), which implies
x_n = x_m + 21
This proves that there are indices m, n such that exactly 21 rehearsals were held during the sequence of consecutive days from day n+1 today m.