MATH 211 Final, Summer 2004

lam cittcan UNIVERSITY LIBRARY. OF BEIRUT Math 211 Final EXAMINATION N. Nahlus Time: 130 minutes Date: August 18, 2004 True —False (Penality: 3 wrong answers cancel 1 right answer) (a) f° (AU B)= f° (A)U f° (B) (b) ffAN B= ffA0 fB® (c) f(f (B)=Bo Im(f) (for every subset B of codomain(f) ) (d) Ris transitive > R© istransitive (Recall: (x,y)eR° iff (V,x)eER ) (ce) R, & R, are transitive > RLUR, is transitive fisl-landgisonto > go f is bijective {A#¢ & AxBCAxC}SBcC (h) f &gareonto = (fg): Xx Y> AxB is onto (where (f,g) (x, y) = (f(x), g(y)) ) and f:X >A & g:Y—B are functions) fofef hasaninverse > f hasaninverse. (f:X —> X is a function) @) f:X 3X isl|-1 => f is bijective 2. Disprove any 4 (FOUR) parts of problem 1. 3. Prove any 3 (Three parts of problem 1). 4. (i) Simplify {p> (q'vr}} A {q> (rv py} (c) Use Boolean Algebra to simplify(B U(A NC) O(DUC)OA 5. Find an explicit formula for s, if sy =1, s,=12, ands, =6s,_,—9s u-2 forn>2 6. Recursively, define a, =1,a,=5, a, =10 and a,=a,.,+ 75a, forn23. Use induction to show that a, 23" forneN. 7. Let fi: Zo >Z, xZ,xZ,be given by f[x],; =([x+2];,1.e+]5s.¢],) - Prove that f is a well-defined function and f isa bijection (1-1 & onto) | In Counting Problems BOX YOUR FINAL ANSWERS 8. In how many ways can distribute 40 identical scholarships over 5 universities {U,, (a) If U, gets atleast 5 scholarships & every other university should gets at least (min) 3 scholarships. BOX YOUR FINAL ANSWER (b) If cach university should gets at most (max) 16 scholarships. BOX YOUR FINAL ANSWER Hint: Take the complement & use Inclusion-Exclusion 9, In how many ways can distribute 30 different scholarships over 5 universities {A, B, C, D, E} (i) If A gets exactly (any) 3 , B gets exactly (any) 7 scholarships, and each of C, D & E gets at least 1 scholarship. BOX YOUR FINAL ANSWER (ii) If A gets exactly (any) 3, B gets exactly (any) 7 scholarships, and each of D & E gets at least 1 scholarship (i.e C may get nothing) Hint: Take 2 cases 10. Suppose s(#)= n° + O(n’) and t(n)=n' +O(n’), +0(n*), Find the smallest possible k such that s(7)¢(#t) = ni4 11. True-—False If false, give a Counter example Reminder: A poset is called normal if each 2 elements have an upper bound and a lower bound meceeee (a) Every chain is a normal poset wennnee (b) Every normal poset is a chain ------- (c) Every maximal element of a normal poset is a maximum element. neeeeee (d) The poset (R,<) is well-ordered . wanna (e) The filing product of chains is a chain. weenee (f) The cartesian product of chains is a chain. soreon- (2) The poset { 0f1,2.3,.4,5,6} — {1,2,3.4,5,6}, C} is a normal poset nesees (h) The poset { g2{1,2,3,4,5,6} — {1,2,3,4,5}, C} is a normal poset oo (i) If a finite poset has a unique maximal element M, then M is a maximum . wees (j) If a infinite poset has a unique maximal element M, then M is a maximum . 12. True- False (Penality: 3 wrong answers cancel | right answer) Reminder: Infinite countable sets are bijective beeeeenenes (a) Zx Zand Qx@Q are bijective sets beceeeeeeees (b) M.,(@) and (Q- N) are bijective sets (c) There exists over 40,000,000 uncountable sets no two of which are bijective (d) INF SEQ{0,1} is an uncountable set (See Notation below) beceeteeeeee (e) R° is bijective to fO(R°) bebe eeneeee () R is bijective totheinterval (0,1) Leceeeeeeeees (g) R is bijective to IRR=R-Q (h) The set of points in the space with integer coordinates is a countable set wonnccennee (i) the set of all polynomials with coefficients in Q is a countable set. Notation: N= The set of natural numbers Z= The set of integers Q- The set of rational numbers R= The set of real numbers M,,,,(S) =The set of nxn matrices with entriesin S §2(S) = The power set of S INFSEQ (S) = The set of all infinite sequences with elements in S