MATH 211 Final, Spring 2009

Math 211 — Spring 2009 Discrete Structures Final exam, June 12, 2009 — Duration: 2 hours GRADES (each problem is worth 12 points): 1 2 3 4 5 6 7 8 TOTAL/96 YOUR NAME: YOUR AUB ID#: PLEASE CIRCLE YOUR SECTION: Section 1 Section 2 Section 3 Section 4 Recitation Th 3:30 Recitation F 8 Recitation Th 11 Recitation Th 5 Ms. Soukiassian Professor Makdisi Ms. Soukiassian Ms. Soukiassian INSTRUCTIONS: 1. Write your NAME and AUB ID number, and circle your SECTION above. 2. Solve the problems inside the booklet. Explain your reasoning precisely and clearly to ensure full credit. Partial solutions will receive partial credit. Each problem is worth 12 points. EACH PART OF A GIVEN PROBLEM CARRIES EQUAL WEIGHT. 3. You may use the back of each page for scratchwork OR for solutions. There are three extra blank sheets at the end, for extra scratchwork or solutions. If you need to continue a solution on another page, INDICATE CLEARLY WHERE THE GRADER SHOULD CONTINUE READING. 4. Open book and notes. CALCULATORS ARE ALLOWED. Turn OFF and put away any cell phones. 5. You do not need to simplify your answers to counting problems — for example, if the answer is �211 30 � + (12!)7 · 6 · 5, just leave it that way. NEW! 6. The problems are ordered in the order of the topics we covered during the semester, NOT in order of increasing difficulty. Take a few minutes at the beginning of the exam to look through the problems and to decide in what order you want to solve the problems. NEW! 7. In each problem, the difficulty of the parts varies even though they have equal weight. EVEN IF YOU CANNOT DO AN EARLIER PART OF A PROBLEM, YOU MAY ASSUME THE RESULT FOR THE LATER PARTS OF THE SAME PROBLEM. GOOD LUCK! i An overview of the exam problems. Each problem is worth 12 points. Each part of a problem is weighted equally. Take a few minutes to look at all the questions, BEFORE you start solving. 1. a) Write statements (i), (ii), and (iii) below in formal logic, using the notation p : “I practice a lot” r : “I win the race” t : “My teammate wins the race” o : “I go to the olympics” m : “We get a medal”. (i) If I practice a lot, then I will win the race and go to the olympics (ii) If my teammate or I wins the race, then we get a medal. (iii) I practice a lot or my teammate wins the race. b) Given statements (i–iii) above, prove (in formal logic) that we get a medal. c) Given statements (i–iii) above, prove (again in formal logic) that: If I do not go to the olympics, then my teammate wins the race. 2. Let f : X → Y be a function, and let A ⊆ X. a) Suppose f is injective. Prove that f(A) ⊆ f(A). (Reminder: f(A) = f(X − A), but f(A) = Y − f(A).) b) Suppose instead that f is surjective. Prove that f(A) ⊆ f(A). 3. We define the function f : Z → Z by f(n) = ⌊n 4 ⌋. a) Find f(n) for every n ∈ {0, 1, 2, 3, 4, 8, 9, 10, 11, 12}. b) Show that ∀b ∈ Z, ��f −1({b}) �� = 4. (Hint: list the elements of f −1({b}).) c) Is f injective? surjective? Explain your answers. d) Find the cardinality |X| of the set X = {A ⊆ Z | f(A) ⊆ {0, 1, 2, 3, 4, 5, 6} ∧ |f(A)| = 3}. 4. The Tutti Frutti Bakery makes manaqish in five flavors: zaatar, apple, banana, cherry, and date. How many ways are there to buy 20 manaqish such that you have as many zaatar manaqish as you like, but no more than 5 each of apple, banana, cherry, and date? (For example, it is possible to buy 4 zaatar, 5 apple, 5 banana, 4 cherry, and 2 date; it is also possible to buy 19 zaatar, 0 apple, 1 banana, 0 cherry, and 0 date.) 5. a) Prove that ⌈x⌉2 is Θ(x2). b) Prove that 2(⌈x⌉2) is O(4(x2)). c) Prove that 2(⌈x⌉2) is NOT O(2(x2)). (Hint: what happens when x = n + 1/2 for n ∈ N?) 6. a) Find the prime factorization of each of 2900 and 1240, and use this to deduce gcd(2900, 1240). b) (UNRELATED) Use the extended Euclidean algorithm to find x0, y0 ∈ Z such that 67x0 + 23y0 = 1. c) Let m ∈ Z. Use the result of part (b) to show that (23 | m) ∧ (67 | m) if and only if (23 · 67) | m. Hint: m = m · 1. Note that you can answer this problem without solving for the specific values of x0, y0. ii 7. a) Let i, j ∈ N satisfy i ≥ 1 ∧ j ≥ 1. Fix i, and prove by induction on j that ij ≥ i + j − 1. (Remark: there is an easier way to prove the above by expanding (i − 1)(j − 1) ≥ 0. However, I want you to prove the result using mathematical induction.) b) Define a sequence a1, a2, a3, . . . recursively by: a1 = 1; ∀n ≥ 2, an = �n−1 k=1 akan−k n = a1an−1 + a2an−2 + · · · + an−1a1 n . Find the values of a2, a3, and a4. (DO simplify the fractions.) c) Use strong induction to prove: ∀n ≥ 1, 0 ≤ an ≤ 1 n. Note that part (a) is useful here. 8. Answer the following exercise in GAP or in pseudocode. You are not allowed to use high-level builtin GAP functions such as ForAny() or Filtered(). However, you are allowed to use IsEmpty(), addfirst(), addlast(), removefirst(), and removelast() just as in the example file example3.txt on recursion. You may also use the functions IsOddInt(), QuoInt(), and RemInt(). Reminders: addfirst([3,1,4,1,5,9], 211) = [211,3,1,4,1,5,9] addlast([3,1,4,1,5,9], 211) = [3,1,4,1,5,9,211] removefirst([3,1,4,1,5,9]) = [1,4,1,5,9] removelast([3,1,4,1,5,9]) = [3,1,4,1,5] IsOddInt(17) = true, IsOddInt(18) = false QuoInt(17,3) = 5, RemInt(17,3) = 2 # because 17 = 5*3 + 2 a) Write a NONrecursive function countodd(ll) that returns the number of odd elements of the list ll. For example, countodd([3,1,4,1,5,9]) = 5 because of the five odd elements 3, 1, 1, 5, 9. This problem should use a loop, and no recursion. b) Write a RECURSIVE version countoddR(ll) of the same function as above. No loops allowed! Reminder: ll[1] is the first element of ll. c) (UNRELATED) Write a RECURSIVE function baseb(N,b) that returns a list [ak,...,a1,a0] of digits of N in base b. Here each ai is an integer with 0 <= ai < N, and we have N = (ak · · · a1a0)b. For example: 13 = (1101)2 and 42 = (2A)16, so we want baseb(13,2) = [1,1,0,1] and baseb(42,16) = [2,10]. You may assume that N >= 0 and that b >= 2. Once again, no loops allowed! iii 1. a) Write statements (i), (ii), and (iii) below in formal logic, using the notation p : “I practice a lot” r : “I win the race” t : “My teammate wins the race” o : “I go to the olympics” m : “We get a medal”. (i) If I practice a lot, then I will win the race and go to the olympics (ii) If my teammate or I wins the race, then we get a medal. (iii) I practice a lot or my teammate wins the race. b) Given statements (i–iii) above, prove (in formal logic) that we get a medal. c) Given statements (i–iii) above, prove (again in formal logic) that: If I do not go to the olympics, then my teammate wins the race. 1 2. Let f : X → Y be a function, and let A ⊆ X. a) Suppose f is injective. Prove that f(A) ⊆ f(A). (Reminder: f(A) = f(X − A), but f(A) = Y − f(A).) b) Suppose instead that f is surjective. Prove that f(A) ⊆ f(A). 2 3. We define the function f : Z → Z by f(n) = ⌊n 4 ⌋. a) Find f(n) for every n ∈ {0, 1, 2, 3, 4, 8, 9, 10, 11, 12}. b) Show that ∀b ∈ Z, ��f −1({b}) �� = 4. (Hint: list the elements of f −1({b}).) c) Is f injective? surjective? Explain your answers. d) Find the cardinality |X| of the set X = {A ⊆ Z | f(A) ⊆ {0, 1, 2, 3, 4, 5, 6} ∧ |f(A)| = 3}. 3 4. The Tutti Frutti Bakery makes manaqish in five flavors: zaatar, apple, banana, cherry, and date. How many ways are there to buy 20 manaqish such that you have as many zaatar manaqish as you like, but no more than 5 each of apple, banana, cherry, and date? (For example, it is possible to buy 4 zaatar, 5 apple, 5 banana, 4 cherry, and 2 date; it is also possible to buy 19 zaatar, 0 apple, 1 banana, 0 cherry, and 0 date.) 4 5. a) Prove that ⌈x⌉2 is Θ(x2). b) Prove that 2(⌈x⌉2) is O(4(x2)). c) Prove that 2(⌈x⌉2) is NOT O(2(x2)). (Hint: what happens when x = n + 1/2 for n ∈ N?) 5 6. a) Find the prime factorization of each of 2900 and 1240, and use this to deduce gcd(2900, 1240). b) (UNRELATED) Use the extended Euclidean algorithm to find x0, y0 ∈ Z such that 67x0 + 23y0 = 1. c) Let m ∈ Z. Use the result of part (b) to show that (23 | m) ∧ (67 | m) if and only if (23 · 67) | m. Hint: m = m · 1. Note that you can answer this problem without solving for the specific values of x0, y0. 6 7. a) Let i, j ∈ N satisfy i ≥ 1 ∧ j ≥ 1. Fix i, and prove by induction on j that ij ≥ i + j − 1. (Remark: there is an easier way to prove the above by expanding (i − 1)(j − 1) ≥ 0. However, I want you to prove the result using mathematical induction.) b) Define a sequence a1, a2, a3, . . . recursively by: a1 = 1; ∀n ≥ 2, an = �n−1 k=1 akan−k n = a1an−1 + a2an−2 + · · · + an−1a1 n . Find the values of a2, a3, and a4. (DO simplify the fractions.) c) Use strong induction to prove: ∀n ≥ 1, 0 ≤ an ≤ 1 n. Note that part (a) is useful here. 7 8. Answer the following exercise in GAP or in pseudocode. You are not allowed to use high-level builtin GAP functions such as ForAny() or Filtered(). However, you are allowed to use IsEmpty(), addfirst(), addlast(), removefirst(), and removelast() just as in the example file example3.txt on recursion. You may also use the functions IsOddInt(), QuoInt(), and RemInt(). Reminders: addfirst([3,1,4,1,5,9], 211) = [211,3,1,4,1,5,9] addlast([3,1,4,1,5,9], 211) = [3,1,4,1,5,9,211] removefirst([3,1,4,1,5,9]) = [1,4,1,5,9] removelast([3,1,4,1,5,9]) = [3,1,4,1,5] IsOddInt(17) = true, IsOddInt(18) = false QuoInt(17,3) = 5, RemInt(17,3) = 2 # because 17 = 5*3 + 2 a) Write a NONrecursive function countodd(ll) that returns the number of odd elements of the list ll. For example, countodd([3,1,4,1,5,9]) = 5 because of the five odd elements 3, 1, 1, 5, 9. This problem should use a loop, and no recursion. b) Write a RECURSIVE version countoddR(ll) of the same function as above. No loops allowed! Reminder: ll[1] is the first element of ll. c) (UNRELATED) Write a RECURSIVE function baseb(N,b) that returns a list [ak,...,a1,a0] of digits of N in base b. Here each ai is an integer with 0 <= ai < N, and we have N = (ak · · · a1a0)b. For example: 13 = (1101)2 and 42 = (2A)16, so we want baseb(13,2) = [1,1,0,1] and baseb(42,16) = [2,10]. You may assume that N >= 0 and that b >= 2. Once again, no loops allowed! 8 Blank sheet. 9 Blank sheet. 10 Blank sheet. 11