Name (PRINTED):

Student ID #:

Section # (or TA's:

name and time)

CMSC 250

Quiz #14 ANSWERS

Wed., May 5, 2004

Write all answers legibly in the space provided. The number of points possible for each question is indicated in square brackets - the total number of points on the quiz is 30, and you will have exactly 15 minutes to complete this quiz. You may not use calculators, textbooks or any other aids during this quiz.

[10 pnts.] Explain how the pigeon hole principle can be used to show that the following is true by giving each of the requested items. Assume you select at random a set of five (not necessarily consecutive) positive integers, can you be sure you have at least two with the same remainder when divided by 4.

The Domain:
ANSWER: The 5 integers chosen.
The Size of the Domain:
ANSWER: 5
The CoDomain:
ANSWER: The possible remainders when that integer is divided by 4.
The Size of the CoDomain:
ANSWER: 4
The Function that Maps this domain to codomain:
ANSWER: f(x) = remainder of (x divided by 4)
[5 pnts.] Is it true or false that the cardinality of the set of the positive odd integers is the same as the cardinality of the set of all integers?

If it is true, prove it by providing any necessary information. If it is false, explain why.
ANSWER: Yes, the cardinalities are the same.
In order to prove they are, you need to have a bijective function that maps from one set to the other.
On such function is:

$\begin{displaymath}f: Z^{+ \wedge odd} \rightarrow Z \mbox{ where } f(x) = \{ {x \equiv_4 3, \frac{x+1}{4}\over x \equiv_4 1, -\frac{x-1}{4}}\end{displaymath}$

Since this function is both one-to-one and onto it is a bijection and the cardinalities must be equal.
[15 pnts.] Assume the following definitions of functions. Give each of the following in simplest terms. (where f and g are both If the requested action is not possible, simply state IMPOSSIBLE and explain why it is not possible.

Assume and
1. $f \circ g =$
  ANSWER: $f(g(x)) = \frac{16x^2+3}{4}$
2. $g \circ f =$
  ANSWER:
3. $f^{-1}=$
  ANSWER: This is not possible because in order to have an inverse function it must be a bijection. This function since if I select $y = \frac{1}{2}$ , x = $\sqrt{2-3} = \sqrt{-1}$ which is not real and therefore is not in .
4. $g^{-1} =$
  ANSWER: $g^{-1}(y) = \frac{y}{4}$