CMSC 250 Homework 13 Spring 2006

Due Wed May 3 at the beginning of your discussion section.

You must write the solutions to the problems single-sided on your own lined paper, with all sheets stapled together, and with all answers written in sequential order or you will lose points.

1. Let $X = \{1,3,5,7\}$ and $Y = \{s,t,u,v,w\}.$ Define $f: X \rightarrow Y$ by the following arrow diagram
   1. write the domain and the co-domain of f. Domain: $\{1,3,5,7\}$
      Co-domain: $\{s,t,u,v,w\}$
   2. what is the range of $f$? $\{s,u,w\}$
   3. what is the inverse image of s? Of u? $s$: $\{3\}$
      $u$: $\{1,5\}$
2. Define f: $R \rightarrow R$ by the rule $f(x) = 3x + 5$ for all $x \in R$.
   1. Is $f$ onto? Prove or give a counterexample. YES. Proof. Let $y$ be arbitrary in ${\bf {R}}$ (the co-domain).     Universal instantiation.
      Let $x = (y-5)/3$.
      Then $x \in {\bf {R}}$ since the reals are closed under subtraction and division.
      So $x$ is in the domain.
      
      $$\begin{eqnarray*} f(x) & ~=~ & f((y-5)/3) ~~~~~\mbox{by substitution} \\ & ~=... ...box{by definition of $f$} \\ & ~=~ & y ~~~~~\mbox{by algebra} \end{eqnarray*}$$
      
      
      
      
      
      $\forall y \in {\bf {R}}\,\exists x \in {\bf {R}}$ such that $f(x) = y$     Universal generalization.
      So $f$ is onto.
      QED
      
   2. Is $f$ one-to-one? Prove or give a counterexample. YES. Proof. Let $a,b$ be arbitrary in ${\bf {R}}$ (the domain).     Universal instantiation.
      $\vert$ Assume $f(a) ~=~ f(b)$
      $\vert$ $3a + 5 ~=~ 3b + 5$     by definition of $f$.
      $\vert$ $3a ~=~ 3b$     by algebra.
      $\vert$ $a ~=~ b$     by algebra.
      $f(a) = f(b) ~\rightarrow~ a = b$      CCW without contradiction
      $\forall a,b \in {\bf {R}}\,\,\,f(a) = f(b) ~\rightarrow~ a = b$     Universal generalization.
      So $f$ is one-to-one.
      QED
   3. Find its inverse function or state why no such function can exist. $y = 3x + 5 ~\rightarrow~ y-5 = 3x ~\rightarrow~ (y-5)/3 = x ~\rightarrow~ x = (y-5)/3$
      So the inverse function is $f^{-1}(x) = (x-5)/3$.
3. 1. How many one-to-one functions are there from a set with three elements to a set with four elements? $4 \cdot 3 \cdot 2 ~=~ 24$.
   2. How many one-to-one functions are there from a set with six elements to a set with five elements? None.
   3. How many onto functions are there from a set with three elements to a set with two elements? ${{3}\choose{2}} + {{3}\choose{1}} ~=~ 3 + 3 ~=~ 6$
   4. How many onto functions are there from a set with four elements to a set with two elements? ${{4}\choose{3}} + {{4}\choose{2}} + {{4}\choose{1}} ~=~ 4 + 6 + 4 ~=~ 14$
4. 1. In a group of 687 people, must there be two who have same first name and last name initials? Why or why not? Yes. There are $26^2 = 676$ possible pairs of initials. Since there are 687 people, by the pigeon hole principle some two people must have the same initials.
   2. If 5 distinct integers are chosen from between 2 and 10 inclusive, must at least 1 of them be a prime? Why or why not? No. Consider the set $\{4,6,8,9,10\}$. It has five numbers, and none of them is prime.
   3. I have a bag filled with marbles. There are 15 red marbles, 9 blue marbles, 12 green marbles, 15 yellow marbles, 4 black marbles, and 3 white marbles. How many marbles would I have to pick out of the bag to guarantee that I have 5 marbles of the same color? $5 \cdot 4 + 3 + 1 ~=~ 24$
5. If each function F and G are defined by formulas find $G\circ F$ and $F \circ G$ and determine whether $G\circ F$ equals $F \circ G$
   1. F(x)$= x^2$; G(x)$= x^2+1$ $G\circ F(x) ~=~ G(F(x)) ~=~ G(x^2) ~=~ (x^2)^2 + 1 ~=~ x^4 + 1$
      $F \circ G ~=~ F(G((x)) ~=~ F(x^2+1) ~=~ (x^2+1)^2 ~=~ x^4 + 2x^2 + 1$
      They are not equal. Let $x = 1$: Then $G\circ F(1) = 2$ and $F \circ G(1) = 4$.
   2. F(x)$= x^3$; G(x)$= x^3$. $G\circ F (x) ~=~ G(F(x)) ~=~ G(x^3) ~=~ (x^3)^3 ~=~ x^6$
      $F \circ G (x) ~=~ F(G(x)) ~=~ F(x^3) ~=~ (x^3)^3 ~=~ x^6$
      They are equal.
6. Let $D = \{x\in{\bf {Z}}\vert 0\leq x < 16\}$. Find examples of functions for each of the parts below. Find algebraic expressions for the functions. You may wish to use algebraic equations taken mod $16$ to construct your functions. Do not list ordered pairs of elements, or the identity function for any of your answers.
   1. Find $h:D\rightarrow D$ such that $h(h(h(x)))=h^{-1}(x)$. Let $h(x) = 15-x$.
   2. Find $f:D\rightarrow D$ such that $\forall x\in D,\,\,f(x)=f(x+5)$, and $f$ is not a constant function. $f(x) = x \bmod 5$
   3. Find $g:D\rightarrow D$ such that $f(f(x))=0$, but $\exists x\in D,\,\, f(x)\neq 0$. $f(x) = \lfloor\frac{x}{15}\rfloor$

Web Accessibility