THEOREM 1

THE PIGEONHOLE PRINCIPLE

If k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.

Proof: Suppose that none of the k boxes contains more than one object. Then the total number of objects would be at most k. Contradiction.

EXAMPLE 1: Among any group of 367 people, there must be at least two with the same birthday, because there are only 366 possible birthdays.

THEOREM 2 THE GENERALIZED PIGEONHOLE PRINCIPLE

If N objects are placed into k boxes, then there is at least one box containing at least éN/kù objects.

Proof: Suppose that none of the boxes contains more than éN/kù - 1 objects. Then, the total number of objects is at most

k(éN/kù - 1) < k(((N/k) + 1) – 1) = N, where the inequality éN/kù < (N/k) + 1 has been used. Contradiction, since there are N objects.

EXAMPLE 4: Among 100 people there are at least é100/12ù = 9 who were born in the same month.

EXAMPLE 6: What is the least number of area codes needed to guarantee that the 25 million phones in a state have distinct 10-digit telephone numbers? Assume that telephone numbers are of the form NXX-NXX-XXXX, where the first three digits form the area, N represents a digit from 2 to 9 inclusive, and X represents any digit.

Solution: There are 8 million different phone numbers of the form NXX-XXXX. Hence, by the generalized pigeonhole principle, among 25 million telephones, at least

é25,000,000/8,000,000ù of them must have identical phone numbers. Hence, at least four area codes are required to ensure that all 10-digit numbers are different.

EXAMPLE 8: show That among any n + 1 positive integers not exceeding 2n there must be an integer that divides one of the other integers.

Solution: Write each of the n + 1 integers a₁, a₂, …, a_n+1 as a power of 2 times an odd integer. In other words, let a_j = 2^kjq_j for j = 1, 2, …, n+1, where k_j is a nonnegative integer and q_j is odd. The integers q₁, q₂, …, q_n+1 are all odd positive integers less than 2n. Since there are only n odd positive integers less than 2n, it follows from the pigeonhole principle that two of the integers q₁, q₂, …, q_n+1 must be equal. Therefore, there are integers i and j such that q_i = q_j. Let q be the common value of q_i and q_j. Then,

a_i = 2^kiq_i and a_j = 2^kjq_j . It follows that if

k_i < k_j, then a_i divides a_j; while if k_i>k_j, then a_j divides a_i.

A subsequence is a sequence obtained from the original sequence by including some of the terms of the original sequence in their original order. A sequence is called strictly increasing if each term is larger than the one that precedes it, and is called strictly decreasing if each term is smaller than the one that precedes it.

THEOREM 3: Every sequence of n² + 1 distinct real numbers contains a subsequence of length n+1 that is either strictly increasing or strictly decreasing.

Proof: See Rosen page 247.

EXAMPLE 9: The sequence 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 contains 10 terms. Note that

10 = 3² + 1. There are four increasing subsequences of length four, namely, 1, 4, 6, 12; 1, 4, 6, 7; 1, 4, 6, 10; and 1, 4, 5, 7. There is also a decreasing subsequence of length four, namely, 11, 9, 6, 5.

The final example shows how the generalized pigeonhole principle can be applied to an important part of combinatorics called Ramsey Theory which deals with the distribution of subsets of elements of sets.

EXAMPLE 10: Assume that in a group of six people, each pair of individuals consists of two friends or two enemies. Show that there are either three mutual friends or three mutual enemies in the group.

Solution: Let A be one of the six people. Of the five other people in the group, there are either three or more who are friends of A, or three or more who are enemies of A. This follows from the generalized pigeonhole principle, since when five objects are divided into two sets, one of the sets has at least

é5/2ù = 3 elements. In the former case, suppose that B, C, and D are friends of A. If any two of these three individuals are friends, then these two and A form a group of three mutual friends. Otherwise, B, C, and D form a set of three mutual enemies. The proof in the latter case, when there are three or more enemies of A, is analogous.