\documentclass[11pt]{exam} \usepackage{graphicx} \usepackage{anysize} \usepackage{dsfont} \usepackage{fullpage} \usepackage{verbatim} \usepackage{url,amsfonts, amsmath, amssymb, amsthm,color, enumerate, multicol} \usepackage{placeins} \printanswers %\noprintanswers \begin{document} \title{ EECS 203: Discrete Mathematics \\ Group Homework 2 (Spring 2016)} \date{Due: May 17, 2016} \author{Answer Key} \maketitle \begin{questions} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[7] Bijections on infinite sets \begin{enumerate}[a)] \item Find a function $f(n): N \rightarrow Z$ which is a bijection (that is both onto and one-to-one). [2] \item Find a function $f(n): Z \rightarrow N$ which is a bijection. [2] \item Find a function $f(x): R \rightarrow R^-$ which is a bijection ($R^-$ is the set of negative reals). [3] \end{enumerate} %% \begin{solution} Note that there are many solutions for these. Here are just a few options that will work. I will prove my function for part a is a bijection. The problem only calls for arguments not formal proofs, so I will simply provide an argument for subsequent parts. \begin{enumerate}[a)] \item $f(n)=\begin{cases} n/2&\text{n is even}\\-(n+1)/2&\text{n is odd}\end{cases}$ To prove f is one-to-one, assume $f(x)=f(y)$. There are 3 options for the parity of x and y: they could both be even, both be odd, or one be even and one be odd. If they are both even, we have that $x/2=y/2$, so multiplying by 2 gives $x=y$. If they are both odd, we have $-(x+1)/2=-(y+1)/2$, so multiplying by $-2$ and subtracting 1 gives $x=y$ If one is odd and one is even (WOLOG, let x be even), we have $x,y\geq0$, so $f(x)=x/2\geq 0/2=0$, while $f(y)=-(y+1)/2<-(0+1)/2=-1/2$. This shows that this case cannot occur because we would have $0\leq f(x)=f(y)<-1/2$, claiming $0<-1/2$. Because every valid case results in $x=y$, $$\forall x,y\in \mathbb{N}, f(x)=f(y)\rightarrow x=y$$ To prove f is onto, let $y$ be an arbitrary element of $\mathbb{Z}$. If $y\geq 0$, $2y\geq 0$, so $2y\in \mathbb{N}$ and $2y$ is even, so $f(2y)=2y/2=y$ as desired. If $y<0$, we know that $y\leq -1$. This means $-2y-1\geq-2\cdot -1-1=2-1=1$, so $-2y-1\in \mathbb{N}$. Finally, because $-2y-1$ is odd, we have that $f(-2y-1)=-(-2y-1+1)/2=-(-2y)/2=y$, as desired. These two situations put together tell us that $$\forall y\in \mathbb{Z}\exists x\in \mathbb{N} f(x)=y$$ Because $f$ is both one-to-one and onto, it is a bijection. \item $f(n)=\begin{cases}2n&n\geq0\\-2n-1&n<0\end{cases}$ The top entry is always even, while the bottom one is odd, so there is no collision between them. Because the function in each case has a unique inverse in $\mathbb{R}$, we can never have different values $x$ and $y$ both non-negative or both negative such that $f(x)=f(y)$. This all tells us that $f$ is one-to-one. Given a value $y\in \mathbb{N}$, if it is even, $y/2$ will be an integer that maps to $y$, while if it is odd, $-(y+1)/2$ is an integer that maps to $y$. Because we can always find a value, $f$ is onto. \item If we want to use a similar trick to the previous parts, we run into the difficulty of separating our outputs. It is still doable, but it becomes rather gross: $$f(x)=\begin{cases}2\lfloor x\rfloor +(x-\lfloor x\rfloor)&x<0\\ -2\lfloor x\rfloor -1+(x-\lfloor x\rfloor)&x\geq0\end{cases}$$ The values $[-1,0)$ map to $2\cdot(-1)+[0,1)=[-2,-1)$ and $[-2,-1)$ map to $2\cdot(-2)+[0,1)=[-4,-3)$. Meanwhile, $[0,1)$ map to $-2\cdot(0)-1+[0,1)=[-1,0)$ and $[1,2)$ map to $-2\cdot(1)-1+[0,1)=[-3,-2)$. Within these segments, they are one-to-one and no two of them overlap, so the whole function is one-to-one. Additionally, each starts right where the last one left off, so it wins up being onto as well.\\ A much much cleaner function to come up with is $$f(x)=-2^x$$ or really any exponential with a base other than 1 negated. This function asymptotically approaches 0 when it goes infinitely in one direction and approaches negative infinity when it goes the other way. This combined with the fact that it is continuous means that $f$ is onto. It is a monotonic function, so it will never turn around and hit the same output value twice, making it one-to-one. \end{enumerate} \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[11] Sets of functions. For each answer provide a brief explanation. \begin{enumerate}[a)] \item How many functions are there that go from a set of 4 elements to a set of 3 elements? [2] \item How many one-to-one functions are there that go from a set of 4 elements to a set of 3 elements? [2] \item How many one-to-one functions are there that go from a set of 3 elements to a set of 4 elements? [2] \item How many onto functions are there that go from a set of 3 elements to a set of 4 elements? [2] \item How many onto functions are there that go from a set of 4 elements to a set of 3 elements? [3] \end{enumerate} %% \begin{solution} \begin{enumerate}[a)] \item Each of the 4 domain elements can independently choose which of the 3 codomain elements to map to. Changing just one of these 4 choices will produce a new function. This means there are $3*3*3*3=3^4=81$ functions. \item To be one-to-one, all 4 of the domain elements must map to a different codomain element. Because we have fewer elements in the codomain than in the domain, no function will be one-to-one, so the answer is 0. \item This is a fairly straightforward count, as similar to part a, each element can be chosen in turn, but this time, we are limited to only those elements that have not been chosen yet. The first has all 4 options. The second had the 3 remaining. The last has the 2 left over. This gives $4*3*2=24$ functions. \item Similar to part b, we find ourselves with no way to hit all 4 of the elements of the codomain using only the images of the 3 elements of the domain, so once again, there are 0 functions. \item When counting these functions, we need to make sure to count every function exactly once. It is all too easy to miss some or to count some of them multiple times. Here are just a couple of my favorite ways to count them. Let the domain of size 4 be $A$ and the codomain of size 3 be $B$:\\ We need to have an element of A reach each element of B, but we are left with 1 extra element of A that we can map to whatever we want. This means there will always be one element of B with 2 things in A that map to it, while the other elements of B each have 1 thing in A that maps to them. There are 3 ways to choose that repeated element of B. Once that is chosen, for each other element of B, we choose which element of A maps to them. The first one has 4 options, while the second one must pick a new entry, so it has only 3. The remaining element of B has the leftover entries of A map to it. This yields $3*4*3=36$ total functions.\\ Alternately, we could blindly choose 1 element of A for each element of B ($4*3*2$) and then for the leftover element of A, pick which element of B it maps to (3 options). In this version, we count every function twice because the double used element of B can pick either preimage in A as the first one that maps to it. All in all, this means there are $4*3*2*3/2=4*3*3=36$ functions. \end{enumerate} \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[5] Provide a deductive argument showing that the premises $\neg (p \wedge q)$, $(p\rightarrow q)$ and $(q\rightarrow p)$ allow you to conclude $(p \vee q)\rightarrow r$. %% \begin{solution}\ \\ \begin{tabular}{lll} i.&$\neg (p\wedge q)$&premise\\ ii.&$p\rightarrow q$&premise\\ iii.&$q\rightarrow p$&premise\\ 1. &$\neg p\vee \neg q$&De Morgans, i\\ 2. &$\neg p\vee q$&Definition of $\rightarrow$, ii\\ 3. &$\neg p\vee \neg p$&Resolution, 1,2\\ 4. &$\neg p$&Idempotent, 3\\ 5. &$\neg q$&Modus tollens, 4, iii\\ 6. &$\neg p\wedge \neg q$&Conjunction, 4,5\\ 7. &$\neg(p\vee q)$&De Morgans, 6\\ 8. &$\neg(p\vee q)\vee r$&Addition, 7, $r$\\ 9. &$(p\vee q)\rightarrow r$&Definition of $\rightarrow$, 8 \end{tabular} \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[7] Say we have five points (xi, yi), each distinct for i= 1 to 5 where each x and y value is an integer. Now say you draw a line connecting each pair of points. Prove that the midpoint of at least one of those lines has an x,y location where both x and y are integers. %% \begin{solution}\ \\ Every integer is even or odd, so there are only 4 ordered pairs of even or odd: (even,even), (even,odd), (odd,even), (odd,odd). If we sort each point into these 4 categories by the parity of its x and y coordinates, we find that because we have more points than categories, there must be at least one category that has at least 2 points in it. Given two points $(x_i,y_i)$ and $(x_j,y_j)$, the midpoint of the line between them is $(\frac{x_i+x_j}2,\frac{y_i+y_j}2)$. If $x_i$ and $x_j$ are both even or both odd, the x coordinate of the midpoint will be an integer (and the same thing for the y coordinates). This means the pair of points in the same category will have a midpoint that has integer coordinates. \end{solution} \end{questions} \end{document}