Page 421 - Discrete Mathematics and Its Applications

400 6 / Counting

Proof: We prove the pigeonhole principle using a proof by contraposition. Suppose that none of
the k boxes contains more than one object. Then the total number of objects would be at most k.
This is a contradiction, because there are at least k + 1 objects.

The pigeonhole principle is also called the Dirichlet drawer principle, after the nineteenth-
century German mathematician G. Lejeune Dirichlet, who often used this principle in his work.
(Dirichlet was not the first person to use this principle; a demonstration that there were at least
two Parisians with the same number of hairs on their heads dates back to the 17th century—
see Exercise 33.) It is an important additional proof technique supplementing those we have
developed in earlier chapters. We introduce it in this chapter because of its many important
applications to combinatorics.
We will illustrate the usefulness of the pigeonhole principle. We first show that it can be
used to prove a useful corollary about functions.

COROLLARY 1 A function f from a set with k + 1 or more elements to a set with k elements is not one-to-one.

Proof: Suppose that for each element y in the codomain of f we have a box that contains all
elements x of the domain of f such that f(x) = y. Because the domain contains k + 1 or more
elements and the codomain contains only k elements, the pigeonhole principle tells us that one
of these boxes contains two or more elements x of the domain. This means that f cannot be
one-to-one.

Examples 1–3 show how the pigeonhole principle is used.
EXAMPLE 1 Among any group of 367 people, there must be at least two with the same birthday, because
there are only 366 possible birthdays. ▲

EXAMPLE 2 In any group of 27 English words, there must be at least two that begin with the same letter,
because there are 26 letters in the English alphabet. ▲

EXAMPLE 3 How many students must be in a class to guarantee that at least two students receive the same
score on the final exam, if the exam is graded on a scale from 0 to 100 points?

Solution: There are 101 possible scores on the final. The pigeonhole principle shows that among
any 102 students there must be at least 2 students with the same score. ▲

G. LEJEUNE DIRICHLET (1805–1859) G. Lejeune Dirichlet was born into a Belgian family living near
Cologne, Germany. His father was a postmaster. He became passionate about mathematics at a young age. He
was spending all his spare money on mathematics books by the time he entered secondary school in Bonn at the
age of 12.At 14 he entered the Jesuit College in Cologne, and at 16 he began his studies at the University of Paris.
In 1825 he returned to Germany and was appointed to a position at the University of Breslau. In 1828 he moved
to the University of Berlin. In 1855 he was chosen to succeed Gauss at the University of Göttingen. Dirichlet
is said to be the first person to master Gauss’s Disquisitiones Arithmeticae, which appeared 20 years earlier.
He is said to have kept a copy at his side even when he traveled. Dirichlet made many important discoveries
in number theory, including the theorem that there are infinitely many primes in arithmetical progressions an + b when a and b are
5
5
5
relatively prime. He proved the n = 5 case of Fermat’s last theorem, that there are no nontrivial solutions in integers to x + y = z .
Dirichlet also made many contributions to analysis. Dirichlet was considered to be an excellent teacher who could explain ideas with
great clarity. He was married to Rebecca Mendelssohn, one of the sisters of the composer Frederick Mendelssohn.