The Pigeonhole Principle∗Nick RogersAugust 28, 2006Pigeonhole Principle. If n + 1 pigeons are distributed among n holes,then at least one of the holes has two or more pigeons.Example 1. Show that if five points are placed in a 1 × 1 square, then there isa pair of points separated by a distance of no more than√22.Example 2. Supp ose that n + 1 distinct numbers are chosen in the range1, 2, . . . , 2n.(a) Show that there is a pair of numbers that are relatively prime (i.e., have nofactors in common).(b) Show that there is a pair of numbers such that one divides the other.Example 3. Show that any set of 10 distinct integers in the range 1, 2, . . . , 99has two disjoint nonempty subsets with the same sum.Example 4. Suppose α ∈ R is irrational. Show that there are infinitely manyrational numberspqsuch thatpq− α≤1q2.Generalized Pigeonhole Principle. If kn + 1 pigeons are distributedamong n holes, then at least one of the holes has k + 1 or more pigeons.Example 5. Suppose that 55 numbers are chosen in the range 1, 2, . . . , 100.Show that there is a pair of numbers that differ by 9.∗I am indebted to Problem-Solving through Problems by Loren C. Larson, from which manyof these problems are drawn.1Problem 1. Suppose that 5 points are placed in an equilateral triangle whoseside length is 1. Show that there is a pair of points separated by a distance ofno more than12.Problem 2. Show that if there are n people at a party, then two of them knowthe same number of people (among those present).Problem 3. Suppose that 20 numbers are chosen from the arithmetic progres-sion 1, 4, 7, . . . , 100. Show that there are two distinct integers in A whose sumis 104.Problem 4. Show that in any group of six people there are either three mutualfriends or three mutual strangers. (Hint: given any of the six people, he or shemust either have three friends or three strangers in the group. Now considerthe relationships among these four people.)Problem 5. Suppose that 19 points are placed in a regular hexagon with sidelength 1. Show that there is a pair of points separated by a distance of no morethan√33.Problem 6. Suppose that 17 people correspond by email, each one with allthe rest. Each pair discusses one of three possible topics: politics, science, orreligion. Show that there are at least three people who all correspond with eachother about the same topic. (Hint: this is like Problem 4, except with threepossibilities for e ach pair of people instead of two.)Problem 7. Suppose that f(x) is a polynomial with integer coefficients, andf(a) = f (b) = f (c) = 2 for distinct integers a, b, and c. Show that there is nointeger d so that f(d) = 3. (Hint: show that f(p) − f(q) is divisible by p − q.)Problem 8. Show that in any set of n integers, there is a nonempty subsetwhose sum is divisible by n.Problem 9. Suppose that 55 numbers are chosen in the range 1, 2, . . . , 100.We have seen that there is a pair that differ by 9. Is there necessarily a pairthat differs by 10? 11? 12? 13?Problem 10. Suppose each point of the plane is colored red or blue. Showthat there is a rectangle all of whose vertices are the same color.Problem 11. Suppose that 64 dots are arranged in an 8 × 8 grid. Is it possibleto divide the plane with 13 lines so that each region contains at most one ofthese points?Problem 12. Given any sequence of mn + 1 real numbers, show that there isan increasing subsequence of length m + 1 or a decreasing subsequence of lengthn +