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

CMSC 250

Quiz #14 ANSWERS

Wed., May 3, 2006

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.

1. [10 pnts.] A gardener plants 600 trees to replenish a forest in 13 days. How many trees must have been planted in one single day to accomplish this? (He wants to do the minimum amount of work each day, so you are figuring how much he needs to accomplish in one day in order to finish the project.) You must justify your answers in terms of the pigeon hole principle: what is the domain, what is the codomain, what is the function and how does this lead to your answer.

   ANSWER:
   The domain is the set of trees. The size of the domain is 600.
   The codomain is the set of days where planting will take place. The size of the codomain is 13.
   The function is the mapping from each tree to the day it will be planted. This is a total function because all 600 trees must be planted on one and only one of the days.
   The pigeon hole principle tells us to find $k$ where $n(D) > k (n(C))$.
   This is true when $k = 46$ because it is true that $600 > 46(13)$.
   Therefore he must plant at least 47 trees on at least one single day of planting.
   

2. [10 pnts.] Give a single total function that fulfills the requirements stated for that one part of the question. The answer can not be an identity function or a constant function. If it is not possible, write the word ``IMPOSSIBLE''.
   1. $A: Z^+ \rightarrow Z$ such that $A$ is one-to-one but not onto.

      
      
      ONE POSSIBLE ANSWER: $A(x) = -x$
      
      

   2. $B: Z \rightarrow Z^+$ such that $B$ is onto but not one-to-one.

      
      
      ONE POSSIBLE ANSWER: $B(x) = if x = 0, B(x) = 1; if x \neq 0, B(x) = \vert x\vert$
      
      

   3. $C: Q \rightarrow Q$ such that $C$ is both one-to-one and onto.

      
      
      ONE POSSIBLE ANSWER: $C(x) = -x$
      
      

3. [10 pnts.] Given the function G defined as follows:
   
   $$G: Q \rightarrow Q, G(x) = x + \frac{1x}{2}$$
   
   

   Determine each of the following by either providing a proof or giving a counter example:

   1. Is G one-to-one?

      
      
      G is one-to-one.
      Proof:
      Let $x_1$ and $x_2$ by arbitrary in Q.
      $\vert$ Asssume $f(x_1) = f(x_2)$
      $\vert x_1 + \frac{1}{2}x_1 = x_2 +\frac{1}{2}x_2$ by using the function definition.
      $\vert x_1(1+\frac{1}{2}) = x_2(1+\frac{1}{2})$ by distribution
      $\vert x_1(1.5) = x_2(1.5)$ by adding rationals
      $\vert x_1 = x_2$ by dividing both sides by 1.5
      $f(x_1) = f(x_2) \rightarrow x_1 = x_2$ by Closing conditional world without contradiction
      $\forall x_1, x_2 \in Q, f(x_1) = f(x_2) \rightarrow x_1 = x_2$ by generalizing from the generic particular
      
      G is one-to-one by the definition of one-to-one.
      
      
      

   2. Is G onto?

      
      
      G is onto
      Proof:
      Let y be arbitrary in Q
      Select x so that $x = \frac{2y}{3}$
      $x \in Q$ because Q is closed under multiplication.
      $f(x) = x + \frac{1}{2}x$ by applying the function definition
      $f(x) = \frac{2y}{3} + \frac{1}{2}(\frac{2y}{3})$ by substitution
      $f(x) = \frac{2y}{3} + \frac{1y}{3}$ by cancelling the 2's
      $f(x) = y$ by adding like parts
      
      $\forall y \in Q, \exists x \in Q, f(x) = y$ by generalizing from the generic particular
      
      G is onto by the definition of onto.

      
      
      

   3. Is G a bijection?

      
      
      Since G is both one-to-one and onto, it is a bijection by the definition of bijection.
      
      

Web Accessibility