MATH 211 Final, Fall 2007

Math 211 — Fall 2007–08 Discrete Structures Final exam, January 31, 2008 — Duration: 2 hours GRADES (each problem is worth 12 points): 1 2 3 4 5 6 7 8 9 10 11 TOTAL/132 YOUR NAME: YOUR AUB ID#: PLEASE CIRCLE YOUR SECTION: Section 1 Section 2 Section 3 Section 4 Recitation W 4 Recitation W 11 Recitation Th 12:30 Recitation Th 3:30 Professor Makdisi Mrs. Karam Mrs. Karam Mrs. Karam 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 ROUGHLY from shortest to longest, but 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. In how many ways may one distribute a standard deck of 52 (distinguishable) playing cards to four (distinguishable) players, each player receiving 13 cards, in such a way that each player receives exactly one ace? 2. We are given three statements: (i) ¬s → ¬p, (ii) s → r, and (iii) q ∧ ¬s → r. Use the given statements to show that (p ∨ q) → r. 3. Let X = {0, 1, 2, . . . , 9}, and consider the function f : X → X given by f(x) = (7x + 1) mod 10. (For example, f(2) = 15 mod 10 = 5.) Show that f is a bijection and give a simple description of the inverse function f −1. 4. Find a simple formula for an given that a0 = a1 = 1 and that for n ≥ 2, we have an = −3an−1 + 10an−2. 5. a) How many times does the following loop repeat? a := x; while a > 1 do a := a/2; od; b) Show that the following nested loop repeats a total of Θ(n log n) times: for x in [1..n] do a := x; while a > 1 do a := a/2; od; od; 6. Let f : X → Y be a function and consider a subset A ⊆ X. a) Show that f(X) − f(A) ⊆ f(X − A). b) Show that if f is injective, then in fact f(X) − f(A) = f(X − A). 7. a) Find the prime factorizations of 444 and 120. Use them to find d = gcd(444, 120). b) Find x0, y0 ∈ Z such that d = 444x0 + 120y0. (Use the extended Euclidean algorithm.) c) Find x1, y1 ∈ Z such that 100d = 444x1 + 120y1. (Your answer can be in terms of x0, y0 from part (b).) d) Show that the following two sets A and B are equal: A = {n ∈ Z | ∃x, y ∈ Z s.t. n = 444x + 120y}, B = {n ∈ Z | n is a multiple of d}. ii 8. Given the following recursively defined function f : N → N: f(0) = 1; for n ≥ 1, f(n) = f(n − 1) + f(⌊n/2⌋). a) Find f(n) for 1 ≤ n ≤ 6. b) Write a recursive program (in GAP or pseudocode) to compute f(n). You may use a function floor() as though it were built in to GAP (or pseudocode). c) Use strong induction to show that ∀n ∈ N, f(n) ≤ 2n. (In fact f(n) is o(2n), but do not try to show this.) 9. For n ∈ N we consider the set S(n) of positive integers ≤ n that are divisible by 2, 3, or 5: S(n) = {k ∈ N | (1 ≤ k ≤ n) ∧ (2|k ∨ 3|k ∨ 5|k)}. a) Write a function (in GAP or in pseudocode) that returns a list whose elements are the elements of S(n). For example, S(12) = [2,3,4,5,6,8,9,10,12]. (Either write a simple loop, or use Filtered().) b) Using inclusion-exclusion and further reasoning, find a formula for the cardinality |S(n)| in terms of n. 10. a) Study the variation of the function f(x) = x−1/2 ln x for x ≥ 1 and find a specific constant A ∈ R such that ∀x ≥ 1, 0 ≤ f(x) ≤ A. b) Find explicit constants c, C, k > 0 such that ∀x ≥ k, cx ≤ x + ln x ≤ Cx. (This shows that x + ln x is Θ(x). Note that you may express c, C, k in terms of A even if you were not able to solve part (a) above.) 11. 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 accompanying the last computer assignment. a) Write a recursive function myforany(ll,P) which returns true if and only if there exists some element x in the list ll for which P(x) is true. b) Write a recursive function myfiltered(ll,P) which returns the sublist of the list ll consisting of all the elements x (in order) in ll for which P(x) is true. iii 1. In how many ways may one distribute a standard deck of 52 (distinguishable) playing cards to four (distinguishable) players, each player receiving 13 cards, in such a way that each player receives exactly one ace? 1 2. We are given three statements: (i) ¬s → ¬p, (ii) s → r, and (iii) q ∧ ¬s → r. Use the given statements to show that (p ∨ q) → r. 2 3. Let X = {0, 1, 2, . . . , 9}, and consider the function f : X → X given by f(x) = (7x + 1) mod 10. (For example, f(2) = 15 mod 10 = 5.) Show that f is a bijection and give a simple description of the inverse function f −1. 3 4. Find a simple formula for an given that a0 = a1 = 1 and that for n ≥ 2, we have an = −3an−1 + 10an−2. 4 5. a) How many times does the following loop repeat? a := x; while a > 1 do a := a/2; od; b) Show that the following nested loop repeats a total of Θ(n log n) times: for x in [1..n] do a := x; while a > 1 do a := a/2; od; od; 5 6. Let f : X → Y be a function and consider a subset A ⊆ X. a) Show that f(X) − f(A) ⊆ f(X − A). b) Show that if f is injective, then in fact f(X) − f(A) = f(X − A). 6 7. a) Find the prime factorizations of 444 and 120. Use them to find d = gcd(444, 120). b) Find x0, y0 ∈ Z such that d = 444x0 + 120y0. (Use the extended Euclidean algorithm.) c) Find x1, y1 ∈ Z such that 100d = 444x1 + 120y1. (Your answer can be in terms of x0, y0 from part (b).) d) Show that the following two sets A and B are equal: A = {n ∈ Z | ∃x, y ∈ Z s.t. n = 444x + 120y}, B = {n ∈ Z | n is a multiple of d}. 7 8. Given the following recursively defined function f : N → N: f(0) = 1; for n ≥ 1, f(n) = f(n − 1) + f(⌊n/2⌋). a) Find f(n) for 1 ≤ n ≤ 6. b) Write a recursive program (in GAP or pseudocode) to compute f(n). You may use a function floor() as though it were built in to GAP (or pseudocode). c) Use strong induction to show that ∀n ∈ N, f(n) ≤ 2n. (In fact f(n) is o(2n), but do not try to show this.) 8 9. For n ∈ N we consider the set S(n) of positive integers ≤ n that are divisible by 2, 3, or 5: S(n) = {k ∈ N | (1 ≤ k ≤ n) ∧ (2|k ∨ 3|k ∨ 5|k)}. a) Write a function (in GAP or in pseudocode) that returns a list whose elements are the elements of S(n). For example, S(12) = [2,3,4,5,6,8,9,10,12]. (Either write a simple loop, or use Filtered().) b) Using inclusion-exclusion and further reasoning, find a formula for the cardinality |S(n)| in terms of n. 9 10. a) Study the variation of the function f(x) = x−1/2 ln x for x ≥ 1 and find a specific constant A ∈ R such that ∀x ≥ 1, 0 ≤ f(x) ≤ A. b) Find explicit constants c, C, k > 0 such that ∀x ≥ k, cx ≤ x + ln x ≤ Cx. (This shows that x + ln x is Θ(x). Note that you may express c, C, k in terms of A even if you were not able to solve part (a) above.) 10 11. 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 accompanying the last computer assignment. a) Write a recursive function myforany(ll,P) which returns true if and only if there exists some element x in the list ll for which P(x) is true. b) Write a recursive function myfiltered(ll,P) which returns the sublist of the list ll consisting of all the elements x (in order) in ll for which P(x) is true. 11 Blank sheet. 12 Blank sheet. 13 Blank sheet. 14