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

Σ(pk - 1) = Σpk - 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 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

  1. V. K. Balakrishnan, Theory and Problems of Combinatorics, Schaum's Outline Series, McGraw-Hill, 1995
  2. A. Engel, Problem-Solving Strategies, Springer Verlag, 1998
  3. D. Fomin, S. Genkin, I. Itenberg, Mathematical Circles (Russian Experience), AMS, 1996
  4. R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
  5. R. Honsberger, Ingenuity in Mathematics, MAA, New Math Library, 1970
  6. R. Honsberger, Mathematical Morsels, MAA, New Math Library, 1978
  7. R. Honsberger, More Mathematical Morsels, MAA, New Math Library, 1991
  8. M. Kac and S. M. Ulam, Mathematics and Logic, Dover Publications, NY, 1992
  9. K. Kuratowski and A. Mostowski, Set Theory, North-Holand, Amsterdam, 1967.
  10. S. Savchev, T. Andreescu, Mathematical Miniatures, MAA, 2003
  11. I. F. Sharygin, Mathematical Vinegrette, Mir, 2002 (in Russian)
  12. D. Wells, The Penguin Book of Curious and Interesting Puzzles, Penguin Books, 1992
  13. P. Zeitz, The Art and Craft of Problem Solving, John Wiley & Sons, 1999

Related material
Read more...

  • Twenty five boys and twenty five girls
  • Pigeonhole in Chess Training
  • Married Couples at a Party
  • Jumping Isn't Everything
  • Zeros and Nines
  • Teams In a Tournament
  • Divisibility of a Repunit
  • Pigeonhole in Clubs
  • |Contact| |Front page| |Contents| |Did you know?| |Algebra|

    Copyright © 1996-2018 Alexander Bogomolny

    71471497