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

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




p.349, icon at Example 6
#1. Each type of machine part made in a factory is stamped with a code of the form “letter-digit-digit”,
where the digits can be repeated. Prove that if 8000 parts are made, then at least four must have the same
code stamped on them.
Solution:
The maximum number of possible codes (pigeonholes) is 26 · 10 · 10 = 2600. But 8000 > 3 · 2600. Therefore
at least four parts must have the same code.




p.349, icon at Example 6
#2. Each student is classified as a member of one of the following classes: Freshman, Sophomore, Junior,
Senior. Find the minimum number of students who must be chosen in order to guarantee that at least eight
belong to the same class.

Solution:

The four classes are the pigeonholes. A group of 28 students could have 7 belonging to each class. But if

there are 29 students, at least 8 must be members of the same class. Therefore, the minimum number of

students who must be chosen is 29.

In other words, we are looking for the minimum number N such that [N/4] = 8. The minimum number is 29.

p.349, icon at Example 6

#3. What is the minimum number of cards that must be drawn from an ordinary deck of cards to guarantee

that you have been dealt

(a) at least three of at least one rank?

(b) at least three aces?

(c) the ace of diamonds?

Solution:

(a) There are thirteen ranks. If you are dealt 26 cards, it is possible that they consist of two cards of each

rank — two aces, two twos, two threes, . . . , two queens, two kings. The 27th card dealt must give you a

hand with three of some rank. (The pigeonholes are the thirteen ranks and the cards are the pigeons.)

(b) In the worst-case scenario, you are dealt 48 cards that include no aces. In order to get three aces, you

would need to be dealt 51 cards.

(c) It is possible that the ace of diamonds could be the last card dealt. Thus, you would need to have all 52

cards dealt to obtain the ace of diamonds.

p.349, icon at Example 6

#4. What is the minimum number of cards that must be drawn from an ordinary deck of cards to guarantee

that you have been dealt

(a) at least three of at least one suit?

(b) at least three clubs?

Solution:

(a) There are four suits. If you are dealt 8 cards, it is possible that they consist of two cards of each suit.

The ninth card dealt must give you three of at least one suit. (The pigeonholes are the four ranks and the

cards are the pigeons.)

(b) In the worst-case scenario, you are dealt 39 cards that include only diamonds, hearts, and spades. In

order to get three clubs, you would need to be dealt three additional cards, making 42 cards.