Pigeonhole Principle and Extensions
The Pigeonhole Principle is one of almost obvious mathematical concepts which are both simple and powerful:
| (1) |
If n > m pigeons are put into m pigeonholes, there's a hole with more than one pigeon.
|
For the proof, assume that the statment is wrong: i.e., assume there are m holes each with at most 1 pigeon. If that's really the case, then summing up the birds across the holes, we would have at most 1 + ... + 1 = m pigeons. However, the given number of pigeons n > m. A contradiction that proves the statement.
The proof, as the principle itself, is very simple and embodies an idea that can be used to prove a generalized statement:
| (2) |
If nk + 1 pigeons, where k is a positive integer, have been put into n holes, then at least one of the holes is crowded with at least k+1 pigeons.
|
Indeed, let's again assume that the statement is wrong. Then each of the holes houses not more than k birds, which means that the total number of birds can't exceed nk. A contradiction.
In the same vein we can establish the following extension:
| (3) |
If p1 + p2 + ... + pn - n + 1 pigeons are placed into n holes, then, for some k, hole k has more than pk pigeons.
|
Once more, assume that the statement is wrong, i.e., assume that, for k = 1, ..., n, hole k contains at most pk - 1 birds. Summing up over all n holes, we find that the total number of the pigeons can't exceed
A contradiction.
Finally, (2) admits a reformulation:
| (2') |
If m pigeons are found in n holes, then at least one of the holes contains at least p = [(m-1)/n] + 1 pigeons,
|
where [x] is the floor function. Indeed, assuming that every hole contains at most p pigeons, we arrive at the contradiction:
| |
| m |  np |
| | n·(m - 1)/n |
| | = m - 1. |
| | < m. |
|
A straightforward reformulation of (2') has been given by E. W. Dijkstra
| |
For a non-empty, finite bag of numbers, the maximum value is at least the average value.
|
(To which we can add the obvious: the average and the maximum values coincide iff the bag only contains equal numbers. Also, the above is obviously equivalent to the assertion that, for a non-empty, finite bag of numbers, the minimum value is at most the average value.)
Example
[Sharygin, p. 12]. Assume in a class of students each of the number of committees contains more than half of all the students. Prove that there is a student who is a member in more than half of the committees.
Let's n be the number of students and m the number of committees in the class. The total committee membership T exceeds m·n/2: T > nm/2. On average, a student is a member in T/n committees and we find that T/n > m/2. Since the maximum value is at least the average value, there is indeed a student who is a member in more than m/2 committees.
Reference
- V. K. Balakrishnan, Theory and Problems of Combinatorics, Schaum's Outline Series, McGraw-Hill, 1995
- A. Engel, Problem-Solving Strategies, Springer Verlag, 1998
- D. Fomin, S. Genkin, I. Itenberg, Mathematical Circles (Russian Experience), AMS, 1996
- R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
- R. Honsberger, Ingenuity in Mathematics, MAA, New Math Library, 1970
- R. Honsberger, Mathematical Morsels, MAA, New Math Library, 1978
- R. Honsberger, More Mathematical Morsels, MAA, New Math Library, 1991
- M. Kac and S. M. Ulam, Mathematics and Logic, Dover Publications, NY, 1992
- K. Kuratowski and A. Mostowski, Set Theory, North-Holand, Amsterdam, 1967.
- S. Savchev, T. Andreescu, Mathematical Miniatures, MAA, 2003
- I. F. Sharygin, Mathematical Vinegrette, Mir, 2002 (in Russian)
- D. Wells, The Penguin Book of Curious and Interesting Puzzles, Penguin Books, 1992
- P. Zeitz, The Art and Craft of Problem Solving, John Wiley & Sons, 1999
Copyright © 1996-2008 Alexander Bogomolny
|
