MATH 211 Final, Fall 2004

-_ Math 211 Final EXAMINATION : N. Nahlus & N. Fuleihan Time: 130 minutes Jan 25, 2005 _ GRADES MAX Name occ ceereee #1: 10 #2,3: 12 #4,5: 12 12 14 12 15 1. (10%) True —False (Penality: 2 wrong answers cancel _1 right answer) (a2) f° AUBUQ= f(A S BY fo (b) fT ANB = f(A SB () fANB)= f(A)O fB) (d) f(f~(B)=Balm(f) (for every subset B of codomain(f) ) R is transitive <=> R° is transitive (f) R, &R, are transitive — R,UR, is transitive go f isbijective ==> f is1-land g is onto f&garebothi-l => (fg): Xx¥Y>AxB is 1-1 (where (f, 8) (%y) = (f00), g(y)) ) and f:X + A & g:Y > B are functions) G) fofof hasaninverse ==> f hasaninverse. (f:X — X is a function) f[:X—>X is onto => f is bijective => _f has an inverse Teal et 2. (6 %) Disprove any 2 (false) parts of problem 1. (Specify ALL DETAILS: What is f A, B, ..etc ?) 3. (6 %) Prove any 2 (true) parts of problem 1. 4. (6%) Simplify (BU(ANC))A(DUC)AA — (int: You may use Boolean Algebra) 5. (6%) Find an explicit formula for s, if s, =1, s, =12, ands, =6s,,—9s,., forn>2 n-2 6, (6%) Recursively, define a, =1,a,=5, a,=10 and a,,,=a,,+ 75a, ., forn2>2. atl n-2 Find the best possible integer r such that a, 2 cr” forneN (Forget about c) (Hint: Proceed as in Induction: Assume it is true for ....... , Prove......., ) 7.(6%) Let f: Z,, > Z, xZ, x Z, be given by f[x],, = ((11x],,[11x],,[11x],) . Prove that fis a Well-defined Bijective function 8. (8 %) In how many ways can we distribute 50 identical scholarships over 4 universities {U,, a) If U, gets at_most 5 scholarships. (Hint: Take the complement, i.e, at least 6 ...) H ip (b) If each university gets at most (max) 20 scholarships. (Hint: Take the complement & use Inclusion- Exchusion. ) (BOX YOUR FINAL ANSWERS) 9. (6%) How many words can be formed by permuting SUCCESSLUNUS (a) with no (further) restrictions (You have 12 letters: 48, 3U, 2C, 1E, 1L, 1N) (b) such your word should NOT end with NUS. 10. (8%) True—False (Penality: 2 wrong answers will cancel 1 right answer) Reminder: A poset is called _directed if each 2 elements have an upper bound and a lower bound. (a) Every chain is a directed poset (b) Every directed poset is a chain (c) Every minimal element of a directed poset is a minimum element. (d) The poset ([50, 00), <) is well-ordered . (e) The set of irrational numbers R - Q can be well-ordered. (f) The filing product of normal posets is a normal poset. (f) The cartesian product of chains is a chain. (g) If a finite poset has a unique minimal element M, then M is a minimum . 11. (4%) Disprove (by a counter example) Any 2 (false) parts of problem 10 above. 6 8 on), 14 | 4,12 +0(nk), 12. (7%) Suppose s(n) = n° +3n4 +O(n3) and t(n)=n Find the smallest possible k such that s(n)t(n) =n (Be_Careful: When you expand, you must have six terms) 13. (8%) True- False (Penality: 2 wrong answers cancel 1 right answer) Reminder: Infinite countable sets are bijective beeeeeeeeees (a) Q® and (Q*-Z’) are bijective sets ve eteee eee ee (b) Any 100 uncountabie sets are bijective be eee nese es (c) INF-SEQ{0,1} is an uncountable set (See Notation below) beseeeeeeees (d) FIN-SEQ(Z) is an uncountable set Leceeeeeeees (e) R° is bijective to f9(R*) be nteeeeees (f) Ris NOT bijective to £9(N) sheee ee neeees (g) R is bijective to Q(R) = All finite subsets of R ceteenenn- (h) 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 nxn §2(S) = The power set of S INF-SEQ (S) = The set of all infinite sequences with elements in S FIN-SEQ (S) = The set of all finite sequences with elements in S a a ‘ 14. (5%) Find (if possible) an Euler path of the following graphs. (To show your path, put a, b,c,... on the edges of your path) 15. (8%) Find 2 non-isomorphic minimal spanning trees of the following weighted graph. Draw the trees separately & clearly (after ....... ). (Use any method)