Chapter Review 279- If a class has 89 students, how many (at least) must have a birthday on the same day
of the week? - Of 15 A's, 20 B's, and 25 C's, how many letters must be chosen so that 12 identical
letters will always be included in the selection? - From the standard deck of 52 cards, how many cards must be chosen so that three
cards from the same suit will always be included in the selection?
4.10.3 Review Questions
- We define three functions, with definitions involving unspecified constants a and b. In
each case, whether the function defined as onto depends on the values of a and b. For
what values of the constants a and b are the following functions onto?
(a) F 1 :Q -Q where F1 (x) =ax + b with a, b E Q
(b) F 2 : Z Z where F 2 (x) =ax + b with a, b E Z(c) F 3 : N N where F 3 (x) =ax + b with a, b E N
2. Let A and B be sets with B 1 , B 2 C_ B, and let F : A -+ B be a function. Show that:
(a) If B1 g B2, then F-'(B 1 ) C F-I(B2).
(b) F-I(Bl U B 2 ) = F-I(B 1 ) U F-I(B 2 ).
(c) F-'(B 1 n B 2 ) = F-'(B 1 ) n F-I(B 2 ).
(d) F-I(B 1 - B 2 ) = F-I(B 1 ) - F-(B2).
(e) F(F-I(B 1 )) c B 1.
(f) Find an example where B 1 C B 2 but F-I(B 1 ) = F-I(B 2 ).
- Show that the set {3, 6, 9, 12, .... ) is countable.
4. Prove that the function F : [0, 1] - (0, 1) defined as F(0) = 1/2, F(1/n) = 1/(n +
2) for n E N and n > 1, and F(x) = x for all other x E [0, 1] is a bijection.- (a) The lattice points in the plane R^2 are the points (x, y) where x and y are both
integers. Prove that there are only countably many lattice points in 1R^2.
(b) The lattice points in three-dimensional space JR^3 are the points (x, y, z) where
x, y, and z are all integers. Prove that there are only countably many lattice points
in R^3.
6. Let p be any natural number and Zp = {0, 1 .... p - 1) be the integers modulo p. For
each integer r where 1 < r < p, the function Fr : Zp -) Zp is the function F, (n) =r. n(mod p). Show that for each p, every Fr is a bijection if and only if p is a prime.
(Hint: Examine cases for which r .n = r. O(mod p), and then use the Pigeon-Hole
Principle.)- Let S be a set of six positive integers with a maximum that is at most 14. Show that
the sums of the elements in all the nonempty subsets of S cannot all be distinct. - If 11 integers are selected from 11, 2, 3 ... , 100), prove that there are at least two, say,
u and v, such that
0 < I 'f-- V- [ < 1 - Uses First-Order Logic: This exercise concerns a result needed for the definition of
subsequence. We took it as obvious there, but it does need proof. So, let X C N.
Part of the job here is to use as simple set theory as possible to define the functions.
You may assume that (i) sets 0, X, N, and N x X exist; (ii) for every i, j E N, (i, j)