Section 5-2 The Pigeonhole Principle-Discrete Mathematics and Its Applications-Page-1

Rosen, Discrete Mathematics and Its Applications, 6th edition
Extra Examples
Section 5.2—The Pigeonhole Principle

p.348, icon at Example 4

#1. Prove that in any group of three positive integers, there are at least two whose sum is even.

Solution:

Consider two pigeonholes, labeled EVEN and ODD. If three positive integers are placed in these pigeonholes, one of the pigeonholes must have at least two integers (say a and b) in it. Thus, a and b are either both even or both odd. In either case, a + b is even.

p.348, icon at Example 4

#2. If positive integers are chosen at random, what is the minimum number you must have in order to guarantee that two of the chosen numbers are congruent modulo 6.

Solution:

In order for a and b to be congruent modulo 6, we must have a mod 6 = b mod 6. But there are six possible values for x mod 6: 0, 1, 2, 3, 4, or 5. Therefore seven positive integers must be chosen in order to guarantee that at least two are congruent modulo 6.

p.348, icon at Example 4

#3. Suppose you have a group of n people (n ≥ 2). Use the Pigeonhole Principle to prove that there are at least two in the group with the same number of friends in the group.

Solution:

Suppose you have a group of n people, and suppose that no two persons have the same number of friends in the group. There are n numbers of possible friends that a person can have: 0, 1, 2, . . ., n−1, where 0 means that the person has no friends in the group, 1 means that the person has exactly one friend in the group, . . . , n − 1 means that the person is friends with all other people in the group. 

It is impossible for the numbers 0 and n − 1 to both occur as “friendship numbers” in a group of n people. To see this, suppose person A has 0 friends and person B has n−1 friends. If the friendship number for B is n − 1, then B must be friends with everyone, including A. But this contradicts the fact that the friendship number for A is 0. Therefore, of the n possible friendship numbers, only n − 1 friendship numbers are available in any group of n people.

Because there are n people in the group and only n − 1 available friendship numbers, by the Pigeonhole Principle at least two people have the same friendship number. That is, at least two people in the group have the same number of friends in the group.

p.348, icon at Example 4

#4. Prove that in any set of 700 English words, there must be at least two that begin with the same pair of letters (in the same order), for example, STOP and STANDARD.

Solution:

The number of possible pairs of letters that can appear in the first two positions is 26 · 26 = 676. Thus, by the Pigeonhole Principle, any set of 677 or more words must have at least two words with the same pair of letters at the beginning of the word.

(Note: In reality, the number 700 can be replaced with a much smaller number, because many combinations of letters do not appear as the two beginning letters of a word. For example, there are no English words that begin with NQ, RR, or TZ.)