MATH 211 Final, Spring 2008

AMERICAN UNIVERSITY OF BEIRUT Faculty of Arts and Sciences Mathematics Department MATH 211 FINAL EXAM Spring 2007-2008 Wednesday June 4, 11:30 am Closed Book, 2H WRITE YOUR ANSWERS ON THE QUESTION SHEET STUDENT NAME ID NUMBER Problem Out of Grade 1 20 2 20 3 20 4 20 5 20 TOTAL 100 1 1. (20 points) Let L(an) = an + 5an−1 + 6an−2. Solve the following recurrence relations. (a) (10 points) Find the general solution of: L(an) = an + 5an−1 + 6an−2 = 4n, n ≥ 2. 2 (b) (10 points) Find the solution to: L(an) = an + 5an−1 + 6an−2 = (−2)n, n ≥ 2 a0 = 0, a1 = 1. 3 2. (20 points) Let a and b be two positive integers greater than 1 and let P be the set of all prime numbers P = {p1, p2, p3, · · · pn · · ·} where p1 = 2, p2 = 3, · · ·. (a) (3 points) Write, in terms of P, the prime number factorization of any integer a, (a ≥ 2). (b) (4 points) Prove that the least common multiplier of a and b, lcm(a, b), and their greatest common divisor gcd(a, b) verify: lcm(a, b) × gcd(a, b) = a × b 4 (c) (3 points) Let a = 882 and b = 308. Find the prime factorization of a and b. (d) (2 points) Find lcm(a, b) and gcd(a, b). (e) (2 points) Are a and b relatively prime (justify your answer). (f) (6 points) Let n and d be positive integers. How many positive integers not exceeding n are divisible by d? (justify your answer) 5 3. (20 points) Solve the following counting problems. (a) (6 points) 8 women and 12 men want to form a committee of 5 persons in which there are at least 2 men and 2 women. i. (3 points) In how many ways can they form the committee? ii. (3 points) If Mr. X and Mrs. Y refuse to work together, how many committees can be formed? (b) (9 points) Four married couples have bought 8 seats in the same row for a concert. In how many different ways can they be seated: i. (3 points) With no restrictions. 6 ii. (3 points) If each couple is to sit together. iii. (3 points) If all the men sit together next to the right of all the women. (c) (5 points) Using pigeonhole principle find the minimum number of students required in Math 211 to be sure that at least six will receive the same grade assuming that there are exactly five possible grades, A, B, C, D and F? 7 4. (20 points) Let A be a finite set of objects, |A| = n and let f : A → N be a function which domain is the power set of A ( Powerset(A) - all subsets of A) and its codomain the set of natural numbers {m ∈ N|0 ≤ m ≤ 2n}, whereby, for s ⊆ A, f(s) is the cardinality of set s (a) (5 points) Let A = {1, 2, 3}. Complete the following table thats assigns the value of f for any subset of A: Subset s of A f(s) (b) (5 points) In general, is f one-to-one? Onto? 8 (c) Let R be a relation on the powerset of A defined by: s R t if f(s) = f(t) i. (6 points) Is R an equivalence relation? ii. (4 points) Find the equivalence class of {a, b} when A = {a, b, c, d}. 9 5. (20 points) For n ∈ N, let Sn be the set of bits strings (i.e. made of o’s and 1’s). (a) (5 points) Give a recursive definition of Sn, by completing the following pseudocode: function S(n) % Return a set of bit strings of length n • if n = 0 then S(n) = {Λ} (Λ is the empty string) • else S(n) = {tx|t ∈ , x ∈ } • end % Note that x is a bit, whereas t is a string Let sn = |Sn|, the cardinality of Sn. Find a recurrence relation on {sn, n ≥ 0} with initial condition then solve this relation. (b) (3 points) Let Tn be the subset of Sn, whereby Tn is the set of strings that have at least one occurrence of the 2 bits pattern 11. Complete the following table: n The set Tn 0 {} (empty set) 1 2 { } 3 { } 10 (c) (6 points) Give a recursive definition of Tn, by completing the following pseudocode (that should use the previous one on S(n)): function T(n) % Return a set of bit strings of length n • if n = 0 or n = 1 then T(n) = {} • else if n ≥ 2, T(n) = {t0|t ∈ }∪{t11|t ∈ }∪{ } • end (d) (6 points) Let tn = |Tn|, the cardinality of Tn. • Using (c) OR independently, find the recurrence relation and the initial conditions verified by {tn}. • Solve the resulting recurrence relation. 11