Discrete Mathematics for Computer Science

The Pigeon-Hole Principle 255

every element of X is mapped to some element of Y, so there are at most k .n elements

in X. M

4.6.2 Proofs of the Pigeon-Hole Principle

Consider again the New England town meeting example. If at most one person left in each
car, then at most 65 people left the garage. This notion is formalized in the contrapositive
to Theorem 1, which is used more often than the theorem itself. The contrapositive is so
important that we state it separately, in two variants. The contrapositive has two names: the
Pigeon-Hole Principle and the Dirichlet Drawer Principle. A more colorful description
of this principle is often given in terms of pigeons and nesting holes. Suppose m pigeons
are placed into n nesting holes where m > n. Then, (at least) one nesting hole contains (at
least) two pigeons.

Theorem 2. (Generalized Pigeon-Hole Principle) Let F : X --* Y be onto where

I X I = m and I Y I = n. Then, there is a y E Y that is the image of at least

elements of X.

Proof. Suppose no y is the image of more than [ ] - 1 elements of X. Then, the total
number of elements in X is at most

m (F -1 <n ( )+ m-1)=

This contradiction proves the result. U

The formulation of the Generalized Pigeon-Hole Principle involved the ceiling func-
tion. It can also be stated using the floor function since for m > n > 0, we have

Example 2. Suppose a class has 89 students. How many students (at least) must have a
birthday in the same month.

Solution. Use the Generalized Pigeon-Hole Principle, and calculate

F128

11-91_-

The same answer can be found by computing

89- 1 8

1 2 +1=8M

Theorem 3. (Pigeon-Hole Principle) Let X and Y be sets, and let F : X -+ Y where
X and Y are finite and I X I > I Y I. There is a y E Y that is the image of at least two
elements of X.