Page 424 - Discrete Mathematics and Its Applications

6.2 The Pigeonhole Principle 403

with 1 ≤ j ≤ 10 not included, so W k can access server S j . (This follows because there are at
least as many available servers S j as there are workstations W j with 1 ≤ j ≤ 10 not included.)
Now suppose there are fewer than 60 direct connections between workstations and servers.
Then some server would be connected to at most
59/10 = 5 workstations. (If all servers were
connected to at least six workstations, there would be at least 6 · 10 = 60 direct connections.)
This means that the remaining nine servers are not enough to allow the other 10 workstations to
simultaneously access different servers. Consequently, at least 60 direct connections are needed.
It follows that 60 is the answer. ▲

Some Elegant Applications of the Pigeonhole Principle

In many interesting applications of the pigeonhole principle, the objects to be placed in boxes
must be chosen in a clever way. A few such applications will be described here.

EXAMPLE 10 During a month with 30 days, a baseball team plays at least one game a day, but no more
than 45 games. Show that there must be a period of some number of consecutive days during
which the team must play exactly 14 games.

Solution: Let a j be the number of games played on or before the jth day of the month. Then
a 1 ,a 2 ,...,a 30 is an increasing sequence of distinct positive integers, with 1 ≤ a j ≤ 45. More-
over, a 1 + 14,a 2 + 14,...,a 30 + 14 is also an increasing sequence of distinct positive integers,
with 15 ≤ a j + 14 ≤ 59.
The 60 positive integers a 1 , a 2 ,...,a 30 , a 1 + 14,a 2 + 14,...,a 30 + 14 are all less than
or equal to 59. Hence, by the pigeonhole principle two of these integers are equal. Because the
integers a j , j = 1, 2,..., 30 are all distinct and the integers a j + 14, j = 1, 2,..., 30 are all
distinct, there must be indices i and j with a i = a j + 14. This means that exactly 14 games
were played from day j + 1today i. ▲

EXAMPLE 11 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 1 ,a 2 ,...,a n+1 as a power of 2 times an odd integer.
k j
In other words, let a j = 2 q j for j = 1, 2,...,n + 1, where k j is a nonnegative integer and q j
is odd. The integers q 1 ,q 2 ,...,q n+1 are all odd positive integers less than 2n. Because there
are only n odd positive integers less than 2n, it follows from the pigeonhole principle that two
of the integers q 1 ,q 2 ,...,q n+1 must be equal. Therefore, there are distinct 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 q and a j = 2 q. It follows
k j
k i
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 clever application of the pigeonhole principle shows the existence of an increasing or a
decreasing subsequence of a certain length in a sequence of distinct integers. We review some
definitions before this application is presented. Suppose that a 1 ,a 2 ,...,a N is a sequence of
, where
real numbers.A subsequence of this sequence is a sequence of the form a i 1 ,a i 2 ,...,a i m
1 ≤ i 1 <i 2 < ··· <i m ≤ N. Hence, a subsequence is a sequence obtained from the original
sequence by including some of the terms of the original sequence in their original order, and
perhaps not including other terms.A sequence is called strictly increasing if each term is larger
than the one that precedes it, and it is called strictly decreasing if each term is smaller than the
one that precedes it.

2
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.