Name (PRINTED):
Student ID #:
Section # (or TA's:
name and time)

CMSC 250

Quiz #14 ANSWERS

Wednesday, Dec 1, 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 20 minutes to complete this quiz. You may not use calculators, textbooks or any other aids during this quiz.

1. [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. How many elements would you need to select from the set of integers $\{1,2,3,4,5\}$ to be sure that you know you must have two distinct pairs of numbers that add to the same sum. Note, one pair of numbers must be made of two numbers that are different and by distinct pairs, it means none of the values are in common.
   The Domain: All possible pairs of the chosen integers.
   
   
   
   
   
   
   

   The Size of the Domain: If there are x integers chosen, the number of pairs is $x \choose 2$. This is equal to $\frac{x(x-1)}{2}$
   
   
   

   The CoDomain: The codomain is the list of all possible sums of these pairs of elements from the set of chosen integers. In other words the integer values between 3 and 9 inclusive.
   
   
   
   
   
   
   

   The Size of the CoDomain: The size of the codomain is $9-3+1 = 7$
   
   
   

   The Function that Maps this domain to codomain: Each pair of integers maps to one and only one element in the codomain based on the value of the sum of the two elements in its pair - since the codomain was built specifically for this purpose, it is a total function.
   
   
   
   This means that by the Pigeonhole principle,
   When n(D) > n(C) the function cannot be one to one.
   $\frac{x(x-1)}{2} > 7$ by substitution
   $x(x-1) > 14$ by multiplying both sides by 2
   This statement becomes true when $x = 5$
   So I can pick 4 and not be sure that I have two pair that add to the same sum take for example the subset $\{1,2,3,5\}$ which has no two pair that have the same sum. I can not though pick all 5.

2. [5 pnts.] What do you need to do to prove that set A is countably infinite if you already know that A is infinite and you know you have another set, B, which you already know is countably infinite?

   
   
   
   
   You would need to find a total function that is a bijection from A to B to know that they have the same cardinality.
   
   
   
   

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

3. [15 pnts.] Assume the following definitions of functions. Give each of the following in simplest terms. (where f and g are both $R^+ \rightarrow R^+$) If the requested action is not possible, simply state IMPOSSIBLE and explain why it is not possible. We are using the book definition that the function and its inverse must both be total functions.
   
   Assume $f(x) = \frac{x^3+1}{2}$ and $g(y) = \frac{1}{2}y$
   
   
   1. $f \circ g = \frac{(\frac{x}{2})^3+1}{2}$
      
      
      
      

   2. $g \circ f =\frac{1}{4}(x^3+1)$
      
      
      
      

   3. $f^{-1}=$ IMPOSSIBLE - the cube root of x is not necessarily real

      
      
      
      
      
      
      
      

   4. $g^{-1}(y) = 2y$

Web Accessibility