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
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 p_{1} + p_{2} + ... + p_{n} - n + 1 pigeons are placed into n holes, then, for some k, hole k has more than p_{k} pigeons. |
Once more, assume that the statement is wrong, i.e., assume that, for
Σ(p_{k} - 1) = Σp_{k} - n.
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 |
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
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
|Contact| |Front page| |Contents| |Did you know?| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
69626093