Discrete Mathematics for Computer Science

280 CHAPTER^4 Functions

exists; (iii) for any x, {x} exists; (iv) for any sets x, y, x U y and x - y exist; and

(v) the collection of elements of any set satisfying some formula of First-Order Logic

(with quantifiers ranging over numbers and sets) exists. You are to use just this much

set theory to show that the function defined by recursion exists. The problem is that

induction may naturally be used to prove that arbitrarily large, finite sets of ordered

pairs exist, but it does not allow one to conclude that a particular infinite set of ordered

pairs exists.

Prove the following:

(a) Suppose X is finite. Let n -I X I. There is at most one increasing function from

{0, 1 ... , n - 1) onto X. (Hint: Suppose there are two, say, F and G. Prove by

induction on i < n that F(i) = G(i).)

(b) If X is infinite, there is at most one increasing function from N onto X.

4.10.4 Using Discrete Mathematics in Computer Science

1. Let F be the function that maps strings of characters and blank spaces onto
   strings of characters by removing all blank spaces and all vowels. For example,

F("dog cat") = "dgct." Let G be the function that maps strings of characters onto

integers such that the value of a string is simply the number of characters in the

string. What is F("george washington")? What is G("george washington")? What is

G o F("george washington")? The function F is a simple example of a compression

technique.

2. Let F : R --* R be a function with F(x) = x^2 .Define a relation R on R such that

x R y for any x, y e R if F(x) = F(y). Prove R is an equivalence relation, and find

its equivalence classes.

3. A computer is used at least one hour a day and at most 102 hours in 12 days. Prove that
   in at least one pair of the six pairs of nonoverlapping consecutive days, the computer
   was used for 17 hours.


4. Triangle ACE is equilateral, with AC = 1. If five points are selected from the interior
   of the triangle, there are at least two whose distance apart is less than one-half. (Note:
   This is a simple version of a problem in the area called computational geometry that
   is actively studied in computer science.)


5. Prove there is no surjection from N to the set of functions with domain and co-
   domain N.


6. Construct a bijection from the set of all polynomials of one variable with coefficients
   in N to N.


7. The circumference of each of two concentric disks is divided into 200 sections. For
   the outer disk, 100 of the sections are painted red, and 100 of the sections are painted
   blue. For the inner disk, the sections are painted red and blue in an arbitrary manner.
   Show that it is possible to align the two disks so that 100 or more of the sections on the
   inner disk have their color matched with the corresponding section on the outer disk.


8. Define a hashing function as a two-stage process that uses Social Security numbers
   as input. The first step is to form a new number consisting of every other digit of
   the Social Security number, starting with the leftmost digit. The hashing value is the
   remainder when this number is divided by 31. For example, 357-75-8564 hashes to

37554 = 13(mod 31). Carry out this hashing procedure for the Social Security num-