Discrete Mathematics for Computer Science

256 CHAPTER 4 Functions

Proof By Theorem 2, ifm= lXI andn= YI within >n, then >_n+1, which

implies

[m ] [n + >l

n -- n - M

Theorem 3 gives a condition that ensures a function is not 1-1 when X and Y are finite

sets.

Example 3. The setting for this example is a room containing 367 people.

(a) At least two of these people have the same birthday.

(b) At least 31 of these people were born in the same month (though possibly in different

years).

(c) Provided no one is more then 121 years old, at least four of these people are the same

age (number of years).

Proof

(a) Let X be the set of people. Let Y be the set of the 366 possible birthdays. Let

BirthDay : X -* Y map each person to his or her birthday. Then, by the Pigeon-Hole Prin-

ciple (Theorem 3), BirthDay is not 1-1.

(b) Let X be the set of people, and let Y be the set of the (^12) months. Let
BirthMonth : X -) Y
be the mapping that takes a person as input and gives the month containing that per-
son's birthday as output. By the Generalized Pigeon-Hole Principle (Theorem 4.2), at least
L (367 - 1)/12j + 1 = 30 + 1 people will have the same birth month.
(c) This proof is left as an exercise for the reader. U
Theorem 4 deals with the question of how far a function is from having a single image
for each element of the domain by guaranteeing that some element will have many images.
Theorem 5 is related to the idea that a function is 1-1.
Theorem 4. Let F:X- YwhereXandY are finite. LetkENandIX >k'IYI.

Then, F is not k to 1.

Theorem 5. Let F : X - Y where X and Y are finite with IXi = Y I. Then, F is 1-1

if and only if F is onto.

Proof

(::) Prove the contrapositive: If F is not onto, then F is not 1-1. If F is not onto, then

there is a y E Y that is not in the range of F. So, F is also a function from X to Y - {y}.

I Y - {Y} I < I Y I = I X 1, so by the Pigeon-Hole Principle, F is not 1-1.

(.:::) Prove the contrapositive: If F is not 1-1, then F is not onto. Suppose F is not 1-1,

and let n = I X I. There are at least two elements of X with the same image. Pick two, and

call them xl and x2. Let the remaining elements of X be X3, X4. Xn. Now, count the

elements in

range(F) = {F(x) :x E X} = {F(xj), F(x 2 ), F(x 3 ), ...., F(xn)}