Page 423 - Discrete Mathematics and Its Applications

402 6 / Counting

EXAMPLE 6 What is the minimum number of students required in a discrete mathematics class to be sure
that at least six will receive the same grade, if there are five possible grades, A, B, C, D, and F?

Solution: The minimum number of students needed to ensure that at least six students receive
the same grade is the smallest integer N such that N/5 = 6. The smallest such integer is
N = 5 · 5 + 1 = 26. If you have only 25 students, it is possible for there to be five who have re-
ceived each grade so that no six students have received the same grade. Thus, 26 is the minimum
number of students needed to ensure that at least six students will receive the same grade. ▲

EXAMPLE 7 a) How many cards must be selected from a standard deck of 52 cards to guarantee that at least
three cards of the same suit are chosen?
b) How many must be selected to guarantee that at least three hearts are selected?

A standard deck of 52
cards has 13 kinds of Solution: a) Suppose there are four boxes, one for each suit, and as cards are selected they are
cards, with four cards of placed in the box reserved for cards of that suit. Using the generalized pigeonhole principle,
each of kind, one in each we see that if N cards are selected, there is at least one box containing at least N/4 cards.
of the four suits, hearts, Consequently, we know that at least three cards of one suit are selected if N/4 ≥ 3. The
diamonds, spades, and
smallest integer N such that N/4 ≥ 3is N = 2 · 4 + 1 = 9, so nine cards suffice. Note that
clubs.
if eight cards are selected, it is possible to have two cards of each suit, so more than eight cards
are needed. Consequently, nine cards must be selected to guarantee that at least three cards of
one suit are chosen. One good way to think about this is to note that after the eighth card is
chosen, there is no way to avoid having a third card of some suit.
b) We do not use the generalized pigeonhole principle to answer this question, because we want
to make sure that there are three hearts, not just three cards of one suit. Note that in the worst
case, we can select all the clubs, diamonds, and spades, 39 cards in all, before we select a single
heart. The next three cards will be all hearts, so we may need to select 42 cards to get three
hearts. ▲

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

Solution: There are eight million different phone numbers of the form NXX-XXXX (as shown
in Example 8 of Section 6.1). Hence, by the generalized pigeonhole principle, among 25 million
telephones, at least 25,000,000/8,000,000 = 4 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 9, although not an application of the generalized pigeonhole principle, makes use
of similar principles.
EXAMPLE 9 Suppose that a computer science laboratory has 15 workstations and 10 servers. A cable can be
used to directly connect a workstation to a server. For each server, only one direct connection to
that server can be active at any time. We want to guarantee that at any time any set of 10 or fewer
workstations can simultaneously access different servers via direct connections. Although we
could do this by connecting every workstation directly to every server (using 150 connections),
what is the minimum number of direct connections needed to achieve this goal?

Solution: Suppose that we label the workstations W 1 ,W 2 ,...,W 15 and the servers
S 1 ,S 2 ,...,S 10 . Furthermore, suppose that we connect W k to S k for k = 1, 2,..., 10 and each
of W 11 ,W 12 ,W 13 ,W 14 , and W 15 to all 10 servers. We have a total of 60 direct connections.
Clearly any set of 10 or fewer workstations can simultaneously access different servers. We see
this by noting that if workstation W j is included with 1 ≤ j ≤ 10, it can access server S j , and
for each workstation W k with k ≥ 11 included, there must be a corresponding workstation W j