The pigeonhole principle (PP) is well known to students of mathematics and computer science and is arguably one of the most widely used tool in combinatorics. In essence, it states that:
Pigeonhole Principle (PP)If n+1 objects are placed in n boxes, then one of the boxes must contain more than 1 object.At first glance, this is a trivial, almost obvious observation. For instance, Edsger Dijkstra remarked on the undeserved status of PP here. But the usefulness of PP is undeniable. Textbook examples of its application include the observation that among 366 people not born on a leapday, 2 of them must share the same birthday. Some more interesting applications can be found here. Chapter 22 in Ref. [3] contains several nontrivial applications of PP.
The flip side of PP is:
(PPb)If n-1 objects are placed in n boxes, then one of the boxes must be empty.An extension of PP is the following [1]:
Extended Pigeonhole Principle (EPP)If nk+1 objects are placed in n boxes, then one of the boxes must contain at least k+1 objects.As Dijkstra remarked, this is in some sense equivalent to the notion that for a finite set of numbers, the maximum value is larger than or equal to the average value. Similarly the minimum value is less than or equal to the average value corresponding to:
(EPPb)If nk-1 objects are placed in n boxes, then one of the boxes must contain at most k-1 objects.A further generalization of PP is the following [2]:
Generalized Pigeonhole Principle (GPP)If nk+s or more objects are placed in n boxes, then for each 0 ≤ m ≤ n there exist m boxes with a total of at least mk + min(s,m) objectsThis corresponds to the fact that for a finite set of numbers, the m largest numbers add up to be equal to or larger than m times the average value (although I would argue that GPP as stated is slightly stronger). Similarly, the m smallest numbers add up to be equal to or less than m times the average value and the corresponding statement to GPP is [2]:
(GPPb)If nk+s or fewer objects are placed in n boxes, then for each 0 ≤ m ≤ n there exist m boxes with a total of at most mk + max(0,s+m-n) objectsThe GPP allows us to show that out of 367 people not born on a leapday, one can find 2 dates and 4 people whose birthday falls on one of these 2 dates. In Dijkstra's article referenced above, the following statement can be proved using EPP:
There are 42 students who are to share 12 computers. Each student uses exactly one computer and no computer is used by more than six students. Then at least five computers are used by three or more students.
If we removed the condition that no computer is used by more than six students, then the conclusion is not necessarily true anymore. However, GPP can be used to prove the following statement:
There are 42 students who are to share 12 computers. Each student uses exactly one computer. Then there are five computers that are used by a total of 20 or more students and there are five computers used by a total of at most 15 students.
[1] K.P. Bogart, Introductory Combinatorics, 3rd ed., Academic Press, 2000.
[2] C. W. Wu, "On graphs whose Laplacian matrix’s multipartite separability is invariant under graph isomorphism," Discrete Mathematics, vol. 310, no. 21, pp. 2811-2814, 2010.
[3] M. Aigner, G. M. Ziegler, Proofs from THE BOOK, 3rd ed., Springer-Verlag, 2004.
Copyright 2010 by Chai Wah Wu.