Name (printed):Student ID #:Section # (or TA’s:name and time)CMSC 250 Quiz #14 ANSWERS Wed., May 5, 2004Write all answers legibly in the space provided. The number of points p os sible for each question is indicatedin square brackets – the total number of points on the quiz is 30, and you will have exactly 15 minutes tocomplete 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 b e used to show that the following is trueby giving each of the requested items . Assume you select at random a set of five (not necessarilyconsecutive) positive integers, can you be sure you have at least two with the same remainder whendivided by 4.The Domain:ANSWER: The 5 integers chosen.The Size of the Domain:ANSWER: 5The CoDomain:ANSWER: The possible remainders when that integer is divided by 4.The Size of the CoDomain:ANSWER: 4The Function that Maps this domain to codomain:ANSWER: f(x) = remainder of (x divided by 4)2. [5 pnts.] Is it true or false that the cardinality of the set of the positive odd integers is the same asthe cardinality of the set of all integers?If it is true, prove it by providing any necessary information. If it is false, explain why.ANSWER: Yes, the cardinalities are the same.In order to prove they are, you need to have a bijective function that maps from one set to the other.On such function is:f : Z+∧odd→ Z where f (x) = {x ≡43,x+14x ≡41, −x−14Since this function is both one-to-one and onto it is a bijection and the cardinalities must be equal.3. [15 pnts.] Assume the following definitions of functions. Give each of the following in simplest terms.(where f and g are both R+→ R+If the requested action is not possible, simply state IMPOSSIBLEand explain why it is not possible.Assume f(x) =x2+34and g(y) = 4ya. f ◦ g =ANSWER: f(g(x)) =16x2+34b. g ◦ f =ANSWER: g(f(x)) = x2+ 3c. f−1=ANSWER: IMP OSSIBLE This is not possible because in order to have an inverse function itmust be a bijection. This function since if I select y =12, x =√2 − 3 =√−1 which is not realand therefore is not in R+.d. g−1=ANSWER: g−1(y)
View Full Document