Pigeonhole Principle

'... I am an American citizen, Delilah. They wouldn't dare touch a hair on my head.'
'They'd have difficulty in finding one.'

W. Somerset Maugham
Ashenden: The British Agent,
Penguin Books, 1977, p. 229

At any given time in New York there live at least two people with the same number of hairs.

The statement above is a direct consequence of the Pigeonhole Principle:

(1)

If m pigeons are put into m pigeonholes, there is an empty hole iff there's a hole with more than one pigeon.

Variously known as the Dirichlet Principle, the statement admits an equivalent formulation:

(2)

If n > m pigeons are put into m pigeonholes, there's a hole with more than one pigeon.

A more formal statement is also available:

(3)

Let |A| denote the number of elements in a finite set A. For two finite sets A and B, there exists a 1-1 correspondence f: A->B iff |A| = |B|.

As may be suggested by the following photo, the formulation may be reversed:

If there are more holes than pigeons, some holes are empty:

pigeonhole principle

The Pigeonhole Principle admits several useful and almost as simple extensions. In fact, the problems below do already use some of alternative formulations.

Proof

Does the Pigeonhole Principle require a proof? It does even though it may be intuitively clear. There are many ways to go about proving it, however proof depends on a set of selected axioms. Far as I know, no one ever chose the Pigeonhole as an axiom. Otherwise, it would have admitted a one line proof. As it is, in the absence of axioms, we may choose assumptions that appear simpler and/or more intuitive, or more deserving perhaps, to be viewed closer to the first principles. The Pigeonhole (as we study it) deals with finite sets. So it is reasonable to assume as fundamental a property that sets finite sets apart from infinite. An infinite set may be equivalent to, i.e., have as many elements as, its proper part. A finite set may not: a finite set containns more elements than any of its proper parts. In addition, it may not be surperfluous to recollect that the symbol |X| for the number of elements in set X may only have sense, provided we may count any finite set, i.e., only if it is possible to determine (by counting, or by a 1-1 correspondence) a natural number N that could be ascribed as the number of elements |X|.

With these preliminaries, assume n < m and that there exists function f from Nm = {1, ..., m} to Nn = {1, ..., n}. This means that,for every k∈Nm, there is an element f(k)∈Nn. Moreover, assume that no element of Nn is associated with more than one element of Nm. In other words, i,j∈Nm and i≠j imply f(i)≠f(j). This exactly means that f(Nm) is a subset of Nn, such that m = |f(Nm)| = |Nm| ≤ |Nn| = n. But this contradicts our assumption that n<m.

Let's return for the moment to the existence of two persons in New York (City) with the same number of hairs. I ran experiments with members of my family. My teenage son secured himself the highest marks sporting, in my estimate, about 900 hairs per square inch. Even assuming a pathological case of a 6 feet (two-sided) fellow 50 inch across, covered with hair head, neck, shoulders and so on down to the toes, the fellow would have somewhere in the vicinity of 7,000,000 hairs which is probably a very gross over-estimate to start with. The Hammond's World Atlas I purchased some 15 years ago, estimates the population of the New York City between 7,500,000 and 9,000,000. The assertion therefore follows from the pigeonhole principle.

Following is a more serious application.

Example 1

Let a be irrational. There exist infinitely many rational numbers r = p/q such that

  |a - r| < q-2

Proof

Let Q be a whole number, a positive integer. Assume also that a>0. Consider the fractional parts {0}, {a}, {2a}, ..., {Qa} of the first (Q + 1) multiples of a. By the pigeonhole principle, two of these must fall into one of the Q (semiopen) intervals [0, 1/Q), [1/Q, 2/Q), ..., [(Q-1)/Q, 1), where, as usual, [A, B) = {x: A ≤ x < B}.

In other words, there are integers s, q1, and q2 such that:

  {q1a}∈[s/Q, (s+1)/Q) and {q2a}∈[s/Q, (s+1)/Q)

Taking q = |q1 - q2| we obtain for some integer p

  |qa - p| < 1/Q

Dividing by q we get |a - p/q| < 1/(Qq) ≤ q-2 since, by definition, 0 < q ≤ Q.

We have yet to demonstrate that the number of such pairs (p, q) is infinite. Assume on the contrary that only for a finite number of ri = pi/qi, i = 1, ..., N, |a - ri| < (qi)-2. Since none of the differences is exactly 0, there exists an integer Q such that |a - ri| > 1/Q for all i = 1, ..., N. Apply our starting argument to this Q to produce r = p/q such that |a - r| < 1/(Qq) ≤ 1/Q. Hence r can't be one of the ri, i = 1, ..., N. On the other hand, as before, |a - r| < q-2 contradicting the assumption that the fractions ri, i = 1, ..., N, were all the fractions with this property.

Example 2

Consider a chess board with two of the diagonally opposite corners removed. Is it possible to cover the board with pieces of domino whose size is exactly two board squares?

Solution

No, it's not possible. Two diagonally opposite squares on a chess board are of the same color. Therefore, when these are removed, the number of squares of one color exceeds by 2 the number of squares of another color. However, every piece of domino covers exactly two squares and these are of different colors. Every placement of domino pieces establishes a 1-1 correspondence between the set of white squares and the set of black squares. If the two sets have different number of elements, then, by the Pigeonhole Principle, no 1-1 correspondence between the two sets is possible.

A Follow-Up

There are several problems naturally related to this one.

Example 3

Prove that however one selects 55 integers 1 ≤ x1 < x2 < x3 < ... < x55 ≤ 100, there will be some two that differ by 9, some two that differ by 10, a pair that differ by 12, and a pair that differ by 13. Surprisingly, there need not be a pair of numbers that differ by 11.

Hint

Given a run of 2n consecutive integers: a + 1, a + 2, ..., a + 2n - 1, a + 2n, there are n pairs of numbers that differ by n: (a+1, a+n+1), (a + 2, a + n + 2), ..., (a + n, a + 2n). Therefore, by the Pigeonhole Principle, if one selects more than n numbers from the set, two are liable to belong to the same pair that differ by n.

Example 4

Prove that if n is odd then for any permutation p of the set {1, 2, ..., n} the product P(p) = (1 - p(1))(2 - p(2))· ...·(n - p(n)) is necessarily even.

Hint

A product of several factors is even if only one of the factor is even.

Example 5

There are several people in the room. Some are acquaintances, others are not. (Being acquainted is a symmetric non-reflexive relationship.) Show that some two people have the same number of acquaintances.

Hint

If there are N people in the room and each has a different number of acquaintances then one is bound to have N - 1 and one 0 acquaintances. This is a contradiction.

Remark

Another application of the Pigeonhole Principle can be found on the shredding the torus page.

Following are a few more problems. (If the solution is available the exclamation mark is clickable - guess why did I say that.) A good half of the problems (of which some are original) were kindly suggested by William A McWorter Jr.

Warmups

  1. Cells of a 15×15 square grid have been painted in red, blue and green. Prove that there are at least two rows of cells with the same number of squares of at least one of the colors.

  2. There are (2n - 1) rooks on a (2n - 1)×(2n - 1) board placed so that none of them threatens another. Prove that any n×n square contains at least one rook.

  3. In every square of a 5×5 board there is a flea. At some point, all the fleas jump to an adjacent square (two squares are adjacent if they share an edge). Is it possible that after they settle in the new squares, the configuration is exactly as before: one flea per square?

  4. 200 points have been cosen on a circle, all with integer number of degrees. Prove that the points there are at least one pair of antipodes, i.e., the points 180° apart.

  5. If each point of the plane is colored red or blue then there are two points of the same color at distance 1 from each other.

  6. The integers 1, 2, ..., 10 are written on a circle, in any order. Show that there are 3 adjacent numbers whose sum is 17 or greater.

  7. Given a planar set of 25 points such that among any three of them there exists a pair at the distance less than 1. Prove that there exists a circle of radius 1 that contains at least 13 of the given points.

  8. Prove that among any five points selected inside an equilateral triangle with side equal to 1, there always exists a pair at the distance not greater than .5.

  9. Let A be any set of 19 distinct integers chosen from the arithmetic progression 1, 4, 7,..., 100. Prove that there must be two distinct integers in A whose sum is 104.

  10. Prove that in any set of 51 points inside a unit square, there are always three points that can be covered by a circle of radius 1/7.

  11. Five points are chosen at the nodes of a square lattice (grid). Why is it certain that at least one mid-point of a line joining a pair of chosen points, is also a lattice point?

  12. Four Numbers, Six Differences, GCD of the Products.

  13. Prove that there exist two powers of 3 whose difference is divisible by 1997.

  14. If 9 people are seated in a row of 12 chairs, then some consecutive set of 3 chairs are filled with people.

  15. Given any sequence of n integers, positive or negative, not necessarily all different, some consecutive subsequence has the property that the sum of the members of the subsequence is a multiple of n.

  16. In every polyhedron there is at least one pair of faces with the same number of sides.

  17. Every polyhedron has a face with two adjacent faces that have the same number of edges.

  18. Given 12 distinct 2-digit integers. Prove there are some two whose difference - a 2-digit number - has equal digits.

  19. What is the largest number of cells of a 6×6 board that could be colored such that no two colored cells touch (not even at a corner)?

  20. 17 students talked of 3 topics. There are 3 students that - between them - talked the same topic.

  21. Seven integers under 127 and their Ratios

  22. Every convex polyhedron has two faces with the same number of sides

Problems

  1. 17 rooks are placed on an 8×8 chessboard. Prove that there are at least 3 rooks that do not threaten each other.

  2. Chinese Remainder Theorem.

  3. Let's mark the centers of all squares of an 8x8 chess board. Is it possible to cut the board with 13 straight lines (none passing through a single midpoint) so that every piece had at most 1 marked point?

  4. Each of the given 9 lines cuts a given square into two quadrilaterals whose areas are in proportion 2:3. Prove that at least three of these lines pass through the same point.

  5. Suppose each point of the plane is colored red or blue. Show that some rectangle has its vertices all the same color.

  6. Suppose each point on a circumference of a circle is colored either red or blue. Prove that, no matter how colors may be distributed, there exist 3 equally spaced points of the same color.

  7. Suppose f(x) is a polynomial with integral coefficients. If f(x) = 2 for three different integers a, b, and c, prove that, for no integer, f(x) can be equal to 3.

  8. Prove that there exists a power of three that ends with 001.

  9. Show that if more than half of the subsets of an n-element set are selected, then some two of the selected subsets have the property that one is a subset of the other.

  10. Let a and b be postive integers, with a < b < 2a. Then, given more than half of the integers in the set {1, 2, ..., a + b}, some two of the given integers differ by a or by b.

  11. Given any 6 points inside a circle of radius 1, some two of the 6 points are within 1 of each other.

  12. Let n be a positive integer greater than 3. Let m be the largest integer in (n+2)/2. Then, given more than m of the integers in the set {1, 2, ..., n}, some three of the integers in the given set have the property that one of the three is the sum of the other two.

  13. If more than half of the integers from {1, 2, ..., 2n} are selected, then some two of the selected integers have the property that one divides the other.

  14. If more than half of the integers from {1, 2, ..., 2n} are selected, then some two of the selected integers are mutually prime.

  15. Given any sequence of mn + 1 real numbers, some subsequence of (m + 1) numbers is increasing or some subsequence of (n+1) numbers is decreasing.

  16. Given any 1000 integers, some two of them differ by, or sum to, a multiple of 1997.

  17. Given any 10 4-element subsets of an 11-set, some two of the subsets intersect in at least two elements.

  18. A person takes at least one aspirin a day for 30 days. If he takes 45 aspirin altogether, in some sequence of consecutive days he takes exactly 14 aspirin.

  19. A theater club gives 7 plays one season. Five women in the club are each cast in 3 of the plays. Then some play has at least 3 women in its cast.

  20. At a party of n people, some pair of people are friends with the same number of people at the party.

  21. Given any 6 integers from 1 to 10, some two of them have an odd sum.

  22. Given a set A ⊂ {1, 2, ..., 100} of ten integers. Prove that it is possible to select two disjoint non-empty subsets of A, S and T, whose members have the same sum.

  23. If a 14×14 0-1 matrix A has 58 1's, then some 2×2 submatrix of A consists of all 1's.

  24. Given 14 or more integers from {1, 2, ... , 28} there exist four of the given integers which can be split into two groups of two with the same sum.

  25. Arrange words HEN, HUT, WIT, SAW, CAR, CUB, MOB, DIM, RED and SON in a circuit so that any two adjacent words share a letter.

  26. The "Math Lotto" betting card is a 6×6 table. The gambler is to mark 6 of the 36 slots in the card. The official result is published with 6 slots chosen as the "LOSING SLOTS". The gambler wins if he doesn't pick any losing slot.

  27. Proizvolov's Identity [Savchev]. In any partition of the first 2N natural numbers into decreasing and increasing sequences of N members each, the sum of absolute values of the differences of the corresponding members of the two sequences is always N2.

  28. Given any nm+1 intervals, there exist n+1 pairwise disjoint intervals or m+1 intervals with a nonempty intersection.

  29. All antichains in Nk with the lexicographic order are finite.

  30. Euclid's theorem: For any two coprime intergers a, b there are two other integers x, y such that ax - by = 1.

  31. In a circle are light bulbs numbered 1 through N, all initially on. At time t, you examine bulb number t, and if it's on, you change the state of bulb t+1 (mod N); i.e., you turn it off if it's on, and on if it's off. If bulb t is off you do nothing. Prove that if you continue around and around the circle in this manner, eventually all the bulbs will again be on.

  32. Twenty five boys and twenty five girls sit around a table. Prove that it is always possible to find a person both of whose neighbors are girls.

  33. A chess master who has 11 weeks to prepare for a tournament decides to play at least one game every day but, in order not to tire himself, he decides not to play more than 12 games during any calendar week. Show that there exists a succession of consecutive days during which the chess master will have played exactly 21 games.

  34. Given two disks, one smaller than the other. Each disk is divided into 200 congruent sectors. In the larger disk 100 sectors are chosen arbitrarily and painted red; the other 100 sectors are painted blue. In the smaller disk each sector is painted either red or blue with no stipulation on the number of red and blue sectors. The smaller disk is placed on the larger disk so that the centers and sectors coincide. Show that it is possible to align the two disks so that the number of sectors of the smaller disk whose color matches the corresponding sector of the larger disk is at least 100.

  35. My wife and I recently attended a party at which there were four other married couples. Various handshakes took place. No one shook hands with oneself, nor with one's spouse, and no one shook hands with the same person more than once. After all the handshakes were over, I asked each person, including my wife, how many hands he (or she) had shaken. To my surprise each gave a different answer. How many hands did my wife shake?

  36. Is it possible to move the counters from the left half of the board to the right half? The only allowed move is to jump over an adjacent (vertically, horizontally, or diagonally) counter. (The jumped over counters are not removed.)

  37. 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.

  38. Any number S is written down, and beneath it are written its multiples 2S, 3S,...up to 10S. Consider the ten digits in any column. There does not appear to be any general law; yet every complete column must contain either a 9 or a 0. Prove this. (In the first column the gaps may be filled by 0's, and the same result holds for all columns.)

  39. 21 girls and 21 boys participate in a math competition. The results show that: a) Each contestant solved at most six problems, and b) For each pair of a girl and a boy, there was at least one problem that they both solved. Prove that there is a problem that was solved by at least three girls and at least three boys.

  40. In a tournament where each team meets every other team once, there are always two teams that played the same number of games.

  41. There is a repunit divisible by 2009.

  42. There are 2009 clubs, each with 45 members, any two of which have exactly one person in common. Show that there is one person who is a member of all the clubs.

  43. Prove that no seven positive integers, not exceeding 24, can have sums of all subsets different.

  44. Suppose 70 students take between them 11 different classes. 15 is the maximum class size. Show that there are at least 3 classes attended by at least 5 students each.

  45. Prove that among any seven points inside or on the boundary of a triangle of area 1, there are three points that form a triangle of area not exceeding 1/4.

  46. Fifteen chairs are evenly placed around a circular table. On the table are the name cards of fifteen guests. After the guests sit down, it turns out that none of them is sitting in front of his own card. Prove that the table can be rotated so that at least 2 guests are simultaneously correctly sitted.

  47. A Math Circle has 31 participant. Their ages are all different and sum up to 434 years. Prove that it is possible to find 20 participants whose total age is at least 280.

  48. Sum of perimeters of regular hexagons inside a square of side 3 is 42. Prove that there are two perpendicular lines such that each one of them intersects at least five of the hexagons.

  49. Every simple polygon with more than three vertices has at least two ears.

  50. Infinitude of Primes - An Impossible Injection

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. A Decade of the Berkeley Mathematical Circle, The American Experience, Volume I, Z. Stankova, Tom Rike (eds), AMS/MSRI, 2008
  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

|Contact| |Front page| |Contents| |Did you know?| |Algebra| |Store|

Copyright © 1996-2017 Alexander Bogomolny

 61141721

Search by google: