※ [本文轉錄自 NTU-Exam 看板 #1LlDCp_4 ] 作者: rod24574575 (天然呆) 看板: NTU-Exam 標題: [試題] 103下 呂育道 離散數學 第二次期中考+解答 時間: Sat Aug 1 22:09:52 2015 課程名稱︰離散數學 課程性質︰選修 課程教師：呂育道 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰2015.05.21 考試時限（分鐘）： 試題 : Discrete Mathematics Examination on May 21, 2015 Spring Semester, 2015 Problem 1 (10 points) Consider the poset ({{1}, {2}, {4}, {1, 2}, {1, 4}, {2, 4}, {3, 4}, {1, 3, 4}, {2, 3, 4}}, ⊆). 1. (3 points) Find the least upper bound of {{2}, {4}}, if it exists. 2. (3 points) Find all lower bounds of {{1, 3, 4}, {2, 3, 4}}. 3. (4 points) Find the greatest lower bound of {{1, 3, 4}, {2, 3, 4}}, if it exists. (Hint: Draw the directed graph for the poset.) Ans: 1. {2, 4}. 2. {3, 4}, {4}. 3. {3, 4}. Problem 2 (10 points) Consider two relations represented by the following matrices: ┌ 1 0 1 ┐ ┌ 0 1 0 ┐ (5 points) 1. │ 0 1 0 │, (5 points) 2. │ 0 1 0 │. └ 1 0 1 ┘ └ 0 1 0 ┘ Determine for each relation whether it is reflexive, irreflexive, symmetric, antisymmetric, and/or transitive. Write down all labels that apply. Recall that a relation R is antisymmetric if (x, y) ∈ R Λ (y, x) ∈ R => x = y for all x, y ∈ A. (Points will be given only when you enumerate all and only those apply.) Ans: 1. Reflexive, symmetric, transitive. 2. Antisymmetric, transitive. Problem 3 (10 points) Find a formula for the convolution of the following two sequences, {(-1)^n}_(n=0,1,2,…), {(-1)^n}_(n=0,1,2,…). Ans: See p.459 of the lecture notes. An alternative is to start from the definition of the convolution with the above two sequences: n k n-k n n n Σ (-1) (-1) = Σ (-1) = (-1) (n+1). k=0 k=0 Problem 4 (10 points) Let n ∈ Z+ with n ≧ 2. Let ψ(n) stand for Euler's totient function, which counts the number of positive integers smaller than n and are relative prime to n. 1. (3 points) Determine ψ(2^n). 2. (3 points) Determine ψ(ψ(2^n)). 3. (4 points) Determine ψ((2p)^n) where p is an odd prime. Ans: 1. ψ(2^n) = 2^n - 2^(n-1) = (2^(n-1))(2-1) = 2^(n-1). 2. ψ(ψ(2^n)) = ψ(2^(n-1)) = 2^(n-1) - 2^(n-2) = (2^(n-2))(2-1) = 2^(n-2). 3. ψ((2p)^n) = ψ((2^n)(p^n)) = ψ(2^n)ψ(p^n) = (2^(n-1))(p^n - p^(n-1)) = (2^(n-1))(p^(n-1))(p-1). Problem 5 (10 points) x^2 Determine the sequence whose generating function is f(x) = ───── 1 - x^3 Ans: As x^2 2 3 6 9 2 5 8 11 f(x) = ─────= x (1 + x + x + x + …) = x + x + x + x + … , 1 - x^3 the sequence is 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, …. Problem 6 (10 points) Let n ≧ 1 be an odd number and A = {1, 2, …, n}. Let σ be a permutation of A on itself (so σ(A) = A). Is the number P = (1 - σ(1))(2 - σ(2))…(n - σ(n)) odd or even or sometimes odd and sometimes even? Justify your answer. Ans: P is even. Notice that for an odd n ≧ 1, in A there are (n-1)/2 even numbers and (n-1)/2 + 1 odd numbers. By the Pigeonhole Principle, there is a least one odd number k ≦ n such that σ(k) is odd, making (k - σ(k)) even and P even as well. Problem 7 (10 points) Solve the following recurrence relations: 1) (5 points) a_n + 2·a_(n-1) + 2·a_(n-2) = 0 with a_0 = 1 and a_1 = 3. 2) (5 points) a_(n+2) = a_(n+1) a_n with a_0 = 1 and a_1 = 2. (Note that it is acceptable if you express a_n in terms of well-known sequences.) Ans: 1) (√2)^n (cos(3nπ/4) + 4·sin(3nπ/4)), n ≧ 0. 2) a_n = 2^(F_n), where F_n = F_(n-1) + F_(n-2) with F_0 = 0 and F_1 = 1. Problem 8 (10 points) Let f: A → B be invertible. Then it is known that there is a function g: B → A such that g。f = 1_A and f。g = 1_B. Show that g is unique. Ans: See pp.286-287 of the lecture notes. Problem 9 (10 points) Suppose A = R^2. Define ￡ on A by (x1, y1)￡(x2, y2) if x1 = x2. Prove that ￡ is an equivalence relation on A. Ans: It suffices to verify the properties of reflexivity, symmetry, and transitiveness. For all (x, y) ∈ A, it is obvious that (x, y)￡(x, y) since x = x. So ￡ is reflexive. If (x1, y1), (x2; y2) ∈ A with (x1, y1)￡(x2, y2), then x1 = x2. So, x2 = x1 and (x2, y2)￡(x1, y1). Hence ￡ is symmetric. Let (x1, y1), (x2, y2) and (x3, y3) be in A with (x1, y1)￡(x2, y2) and (x2, y2)￡(x3, y3). Then (x1, y1)￡(x2, y2) implies x1 = x2, and (x2, y2)￡(x3, y3) implies x2 = x3. It follows that x1 = x3, so (x1, y1)￡(x3, y3) and ￡ is transitive. Problem 10 (10 points) Consider x_1 + x_2 + x_3 + x_4 = 19. Determine the number of integer solutions if 0 ≦ x_i ＜ 8 for all 1 ≦ i ≦ 4. ╭ n+r-1 ╮ (Hint: There are │ │ integer solutions to x_1 + x_2 + … + x_n = r, ╰ r ╯ x_i ≧ 0 for all 1 ≦ i ≦ n.) Ans: Let c_i denote the condition x_i ≧ 8 for all i. By the inclusion-exclusion ___ ___ ___ ___ ╭ 22 ╮ ╭ 4 ╮╭ 14 ╮ ╭ 4 ╮╭ 6 ╮ principle, N(c_1 c_2 c_3 c_4) = │ │ - │ ││ │ + │ ││ │. ╰ 19 ╯ ╰ 1 ╯╰ 11 ╯ ╰ 2 ╯╰ 3 ╯ Or you can use the generating function method on p.466 of the lecture notes. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.254.199 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1438438195.A.FC4.html

※ 發信站: 批踢踢實業坊(ptt.cc) ※ 轉錄者: simonmao (140.112.16.145), 04/29/2016 14:28:29