Name (PRINTED):

Student ID #:

Section # (or TA's:
name and time)  

CMSC 250 Exam #3 Friday, Dec. 3, 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 exam is 100, and you will have exactly 50 minutes to complete this exam. You may not use calculators, textbooks or any other aids during this exam. If you need more space for any answer, ask for an extra paper - these extra papers must be turned in and you must mark them so we can find the answer corresponding to a question. The ``cheatsheet'' (which is the last page of the exam) can be ripped off and used during the exam. Leave the paper closed this side up on your desk until you are told to start. Make sure you are in your assigned seat with all cellphones and pagers turned off. Make sure you have writing instruments and your picture ID out on your desk.


















**** This area is for grading purposes (points lost per problem)- Do not write below this line ****





\begin{picture} % latex2html id marker 64 (400,0) \setlength{\unitlength}{.525... ...}\stepcounter{ctr}}} }\ \put(250,20){\makebox(40,20)[bc]{Total}} \end{picture}
  1. [14 pnts] For each of the following functions write either yes or no into the blank provided as indicated and then justify your answer when requested. JUSTIFICATION IS NEEDED FOR BOTH YES AND NO ANSWERS. Justification for a universal statement that is true means that you must have a formal proof.
    1. $f: Z \rightarrow Z $ where $f(x) = 2x -1$

      1. YES Is this a total function ?(yes or no).


      2. NO Is this function onto? (yes or no)

      3. JUSTIFY YOUR ANSWER:






        Let $f(x) = 6$.
        $6 = 2x - 1$ by substitution
        $7 = 2x$ by adding 1 to both sides
        $\frac{7}{2} = x$ by dividing both sides by 2
        This is a problem because $\frac{7}{2} \not\in Z$






      4. YES Is this function one-to-one? (yes or no)

      5. JUSTIFY YOUR ANSWER:






        Let $x_1$ and $x_2$ be arbitrary in Z.

        Assume $f(x_1) = f(x_2)$
        $2x_1 -1 = 2x_2 - 1$ by substitution
        $2x_1 = 2x_2$ by adding 1 to both sides
        $x_1 = x_2$ by dividing both sides by 2

        $f(x_1) = f(x_2) \rightarrow x_1 = x_2$ by closing conditional world

        $\forall x_1, x_2 \in Z, f(x_1) = f(x_2) \rightarrow x_1=x_2$ by generalizing from the Generic Particular

        Therefore f is one-to-one by the definition of one-to-one.






    2. $g: R \rightarrow R^{\leq 0}$ where $g(x) = - x^2$

      1. YES Is this a total function ?(yes or no).


      2. YES Is this function onto? (yes or no)

      3. JUSTIFY YOUR ANSWER:






        Let y be arbitrary in $R ^{\leq 0}$
        Select x = $\sqrt{-y}$
        Since $y \in R^{\leq 0}, -y \in R^{\geq 0}, $ therefore $x \in R$.
        $f(x) = f(\sqrt{-y})$ by substitution
        = $- (\sqrt(-y))^2$ by substitution
        = $- (-y) $ by squaring a squareroot
        = $y$ by double negative

        $\exists x \in R, f(x) = y$ by existential generalization
        $\forall x \in R^{\leq 0}, \exists x \in R, f(x) = y$ by generalizing from the generic particular.

        Therefore g is onto by definition of onto.






      4. NO Is this function one-to-one? (yes or no)

      5. JUSTIFY YOUR ANSWER:






        Let $x_1 = 1$ and let $x_2 = -1$.
        $f(x_1) = f(1) = - 1^2 = -1$ and $f(x_2) = f(-1) = - (-1)^2 = -1$
        It is true that $f(x_1) = f(x_2)$ because $-1 = -1$
        but it is false that $1 = -1$






  2. [10 pnts.] Assume you have two finite sets X and Y. The set X has 10 members, and the set Y has 5 members.


    1. Assume you have created a set named F which is the set of all possible total functions from X to Y. What is the size of the set F?


      $5^{10}$
      For each of the 10 things in the domain, each must select one and only one of the 5 things in the codomain.


    2. Assume you have created another set named R which is the set of all possible relations from X to Y. What is the size of the set R?


      $2^{50}$
      There are 50 possible arrows connecting the elements of the domain to the elements in the codomain. This is the size of $X \times Y$, and a relation must be s subset of $X \times Y$. Therefore each of these arrow have two possibilities, either it is there in the relation or it is not.


  3. [9 points] For each of the following mark which properties the relation has with a Y if it has that property or a N if it does not.
  4. [20 pnts] Prove that the following statement is true or give a specific counter example to show that it is false. When doing a proof, you must give reasons for all steps.

    \begin{displaymath}\forall A,B,C,D \in \{sets\}, (A \cap B) \times (C-D) \subseteq (A \times C) \cup (B \times C)\end{displaymath}

    Let A, B,C and D be arbitrary sets

    Let (x,y) be arbitrary in the Universe

    Assume $(x,y) \in (A \cap B) \times (C-D)$ $x \in A \cap B$ by def of Cartesian Product
    $y \in C-D$ by def of Cartesian Product
    $x \in A \wedge x \in B$ by definition of intersection
    $y \in C \wedge y \not\in D$ by definition of set difference
    $x \in A \wedge y \in C$ by conjunctive simplification and conjunctive addition
    $(x,y) \in A \times C $ by definition of cartesian product
    $(x,y) \in A \times C \vee (x,y) \in B \times C$ by disjunctive addition
    $(x,y) \in (A \times C) \cup (B \times C)$ by definition of union

    $(x,y) \in (A \cap B) \times (C - D) \rightarrow (x,y) \in (A \times C) \cup (B \times C) $ by Closing Conditional World
    $\forall (x,y) \in U, (x,y) \in (A \cap B) \times (C - D) \rightarrow (x,y) \in (A \times C) \cup (B \times C) $ by generalizing from the Generic Particular
    $(A \cap B) \times (C - D) \subseteq (A \times C) \cup (B \times C) $ by definition of subset
    $\forall A,B,C,D \in \{sets\},(A \cap B) \times (C - D) \subseteq (A \times C) \cup (B \times C) $ by generalizing from the Generic Particular
  5. [20 pnts] Assume you are working for a charity group and your assignment is to buy and distribute toys to the children of an orphanage. You may assume there are 20 children, 12 girls and 8 boys (and all the children are distinguishable). Answer each of the following questions. The specific details given in one question do not affect the others questions in any way. Partial credit is possible only if you describe what you are thinking. Your answer does not need to be taken to an numeric value, but it does need to be given in a form that has only addition, subtraction, multiplication, division, factorials and exponents.
    1. Assume you purchase the correct number of toys so that each child gets exactly one where each of the boys will receive a truck and each of the girls will receive a doll. The trucks are indistinguishable from each other (you purchased 8 copies of the same truck). The dolls are distinguishable from each other (they are all different). How many ways can you distribute these to the children assuming a girl must receive a doll and a boy must receive a truck? ANSWER: $12!$
      All boys get trucks so there is only one way to do that.
      Since all of the dolls are different (and all of the girls are different), you must put one in order based on the other remaining stationary. This would be the same as the number of ways to order the 12 dolls purchased.
    2. You are at the toy store where there is a supply of at least 20 of each of the 5 kinds of toys they sell (they have yo-yo's, slinkies, jacks, balls and jumpropes). All of these toys are appropriate for either boys or girls. How many ways can you walk out of the toystore carrying enough toys so that each child gets exactly one gift? ANSWER: $\frac{(20+(5-1))!}{20!(5-1)!}$
      Since we are only looking at the ways you walk out of the store, we are not concerned with how they are distributed to the children. This makes it a situation of dividing the 20 indistinguishable x's into the categories of the 5 kinds of toys.
    3. You have had 25 toys donated. All 25 toys are different from each other. How many ways can you distribute the 25 toys to the 20 children if you want each child to get one and only one toy. Assume you are not concerned with what toy the child might like or what toy is age appropriate for that child and that you get to keep the remaining 5 toys yourself. ANSWER: $\frac{25!}{5!}$
      This is actually $P(25,20)$. This means we would order all 25 toys in a line and then not care about the orders of the last five (the ones you are going to keep for yourself).
    4. Assume instead of bringing toys to these children, you are planning to take them in groups of size 5 to the toy store to pick out their own toys. How many ways can you divide them into groups of 5? ANSWER: $\frac{20!}{(5!)^4}$
      You can see this as selecting the ones for the first group and then the ones for the second group, etc. This would be ${20 \choose 5}{15 \choose 5}{10 \choose 5}{5 \choose 5}$. This is the same as considering the order of all 20 children, then drawing the cutting lines to determine the groups and then saying that you need to disregard the order of the members within each group.
    5. Assume you are having a large group picture taken of all of the children with their toys (for promotional purposes for your charity). You have 10 children that are tall who will be in the back row of the picture and 10 children who are short who will be in the front row of the picture. (You have exactly 2 rows of children in the picture.) How many different ways can you position the children for the picture? ANSWER: $(10!)^2$
      The multiplication rule is applied in order to say there are two separate tasks that need to be done - order the back row and order the front row. There are $10!$ ways to order the back row, and there are $10!$ ways to order the front row. Both of these tasks must be done in order to be ready to take the picture - therefore we multiply them.
    6. Assuming the picture line up from the previous question but you have a problem that three of the short children Alex, Barry and Carl are difficult and cause problems if all of these three are standing together during the photo session. What is the probability that these three are standing together if you assume that you have arranged the children completely randomly for the picture? ANSWER: $\frac{10!8!3!}{(10!)^2} = \frac{8!3!}{10!} = \frac{1}{15}$
      The denominator is the answer from the previous question since it is the number of ways to arrange the children and all arrangements are equally likely.
      The numerator has the $10!$ to indicate the number of ways to arrange the backrow.
      The numerator had the $8!$ to indicate the number of ways to arrange the front row treating the 3 problem children as a single unit that stays together in the rearranging.
      The numerator also has the $3!$ to indicate the number of ways to arrange the three problem children since the previous part treated them as a single unit these rearrangements have not previously been considered.
  6. [15 pnts] Prove that the following statement is true or give a specific counter example to show that it is false. If you decide to prove it true, you may use all of the rules on the attached sheet and do not need to prove it at by using the member level and the additional definitions that do not appear on the sheet. When doing a proof, you must give reasons for each step.

    \begin{displaymath}\forall A,B,C \in \{sets\}, (A - B) - (A - C) = A \cap (C - B)\end{displaymath}

    $(A-B)-(A-C)$
    $(A \cap B') \cap (A \cap C')'$ by alt rep of set diff
    $(A \cap B') \cap (A' \cup C)$ by DeMorgans and double complement
    $B' \cap (A \cap (A' \cup C))$ by commutativity and associativity
    $B' \cap ((A \cap A') \cup (A \cap C))$ by distribution
    $B' \cap ( \emptyset \cup (A \cap C))$ by intersection with complement
    $B' \cap (A \cap C)$ by union with empty set
    $A \cap (C \cap B')$ by associativity and commutativity
    $A \cap (C - B)$ by Alternative representation of set difference
  7. [12 pnts] Assume you are creating a subset from the set of the 1 digit positive integers $\{1,2,3,4,5,6,7,8,9\}$. Answer the following sequence of steps to show how you can use the pigeon hole principle to answer the question about how many you would need to have in your subset to know for sure that you have two in the subset that sum to 8.
    1. Describe the contents of the domain you would like to use. ANSWER: The set of integers chosen.






    2. Describe the contents of the codomain you would like to use. ANSWER: $\{\{1,7\},\{2,6\},\{3,5\},\{4\},\{8\},\{9\}\}$






    3. What is the size of that codomain that you just described? ANSWER: 6







    4. Describe a total function that maps elements in the domain you just described to elements in the codomain you just described. ANSWER: each chosen integer is mapped to the one set that contains that value. In other words, $f(x) = M$ where $x \in M$.






    5. Now apply the pigeon hole principle and answer the question `` what is the minimum size the domain can be where you are sure you know that you must have two distinct numbers whose sum is 8?'' ANSWER: Since when the size of the domain is larger than the size of the codomain we know that the function can not be one-to-one, when the size of the domain is 7 (it is larger than the codomain) and the function can not be one-to-one. When the function is not one-to-one, we know that we have two integers in our domain set that map to the same set that is a member of the codomain. When we have two integers in the set of selected integers that map to the same element in the codomain, we know we have two whose sum is 8 because that is the way the codomain was created.

Kin-Keung Ma 2004-12-06

Web Accessibility