Page 420 - Discrete Mathematics and Its Applications

6.2 The Pigeonhole Principle 399

71. Use mathematical induction to prove the sum rule for m is made up of six 32-bit blocks. Another of the 14 header
tasks from the sum rule for two tasks. fields is the 16-bit-long total length field (denoted by
72. Use mathematical induction to prove the product rule TOTAL LENGTH), which specifies the length in bits
for m tasks from the product rule for two tasks. of the entire datagram, including both the header fields
and the data area. The length of the data area is the total
73. How many diagonals does a convex polygon with n sides
have? (Recall that a polygon is convex if every line seg- length of the datagram minus the length of the header.
ment connecting two points in the interior or boundary of a) The largest possible value of TOTAL LENGTH
the polygon lies entirely within this set and that a diago- (which is 16 bits long) determines the maximum
nal of a polygon is a line segment connecting two vertices total length in octets (blocks of 8 bits) of an Internet
that are not adjacent.) datagram. What is this value?
b) The largest possible value of HLEN (which is 4 bits
74. Data are transmitted over the Internet in datagrams,
which are structured blocks of bits. Each datagram con- long) determines the maximum total header length
tains header information organized into a maximum in 32-bit blocks. What is this value? What is the
of 14 different fields (specifying many things, including maximum total header length in octets?
the source and destination addresses) and a data area that c) The minimum (and most common) header length is
20 octets. What is the maximum total length in octets
contains the actual data that are transmitted. One of the
of the data area of an Internet datagram?
14 header fields is the header length field (denoted by
HLEN), which is specified by the protocol to be 4 bits d) How many different strings of octets in the data area
long and that specifies the header length in terms of 32-bit can be transmitted if the header length is 20 octets
blocks of bits. For example, if HLEN = 0110, the header and the total length is as long as possible?

6.2 The Pigeonhole Principle

Introduction

Suppose that a flock of 20 pigeons flies into a set of 19 pigeonholes to roost. Because there are
20 pigeons but only 19 pigeonholes, a least one of these 19 pigeonholes must have at least two
pigeons in it. To see why this is true, note that if each pigeonhole had at most one pigeon in it,
at most 19 pigeons, one per hole, could be accommodated. This illustrates a general principle
called the pigeonhole principle, which states that if there are more pigeons than pigeonholes,
then there must be at least one pigeonhole with at least two pigeons in it (see Figure 1). Of
course, this principle applies to other objects besides pigeons and pigeonholes.

THEOREM 1 THE PIGEONHOLE PRINCIPLE If k is a positive integer and k + 1 or more objects
are placed into k boxes, then there is at least one box containing two or more of the objects.

(a) (b) (c)

FIGURE 1 There Are More Pigeons Than Pigeonholes.