課程名稱︰離散數學 課程性質︰選修 課程教師：呂育道 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰2013.05.09 考試時限（分鐘）： 試題 : Discrete Mathematics Examination on May 9, 2013 Spring Semester, 2013 Note: You may use any results proved in the class unless stated otherwise. Problem 1 (10 points) Let A = {1, 2, 3, 4, 5}. 1) (5 points) How many bijective functions f: A → A satisfy f(1) ≠ 1? 2) (5 points) How many functions f: A → A are invertible? Ans: 1) 4 × (4!) = 96. 2) 5! = 120. Problem 2 (10 points) x^3 Determine the sequence generated by f(x) = ─────. 1 - x^2 x^3 Ans: As f(x) = ───── = (x^3) (1 + x^2 + x^4 + …) = x^3 + x^5 + x^9 + …, 1 - x^2 f(x) generates the sequence {0, 0, 0, 1, 0, 1, 0, …}. Problem 3 (10 points) Suppose that n, r ∈ Z+ and 0 ＜ r ≦ n. Prove that ╭ -n ╮ r╭ n + r - 1 ╮ │ │ = (-1) │ │. ╰ r ╯ ╰ r ╯ Ans: See p. 451 of the slides. Problem 4 (10 points) Find the generating function and pinpoint the coefficient for the number of integer solutions to the equation c_1 + c_2 + c_3 + c_4 = 10 where c_1 ≧ -3, c_2 ≧ -4, -5 ≦ c_3 ≦ 5, and c_4 ≧ 0. (There is no need to calculate the numerical value of the coefficient. You only have to answer like "the coefficient of x_i (you specify i) in the generating function … (you write down the function).") Ans: Let x_1 = c_1 + 3, x_2 = c_2 + 4, x_3 = c_3 + 5, and x_4 = c4, then the original problem is equivalent to x_1 + x_2 + x_3 + x_4 = 22 where x_1, x_2, x_4 ≧ 0, and 0 ≦ x_3 ≦ 10. Consequently, the answer is the coefficient of x^22 in the generating function (1 + x + x^2 + …)^3 (1 + x + x^2 + … + x^10). Problem 5 (10 points) Let n ∈ Z+. 1) (5 points) Determine ψ(2^n). 2) (5 points) Determine ψ((2^n)p) where p is an odd prime. Ans: 1) ψ(2^n) = 2^n × (1 - 1/2) = 2^(n-1). 2) ψ((2^n)p) = (2^n)p × (1 - 1/2) × (1 - 1/p) = (2^(n-1))(p-1). Problem 6 (10 points) Assume that 11 integers are selected from S = {1, 2, 3, …, 100}. Show that there are at least two, say x and y, such that 0 < |√x - √y| < 1. (Hint: You may consider the pigeonhole principle and for any t ∈ S, 0 < √t < 10.) Ans: For any t ∈ S, 0 < √t < 10, so there must be two integers x and y such that floor(√x) = floor(√y). Thus, the claim holds. Problem 7 (10 points) Suppose |A| = m. How many relations on A are there which are irreflexive and symmetric? Ans: For any (x, y) ∈ A and x ≠ y, the number of decisions to make for ╭ m ╮ (m^2 - m) ((m^2 - m)/2) membership in R is │ │ = ──────. Thus, there are 2 ╰ 2 ╯ 2 relations which are irreflexive and symmetric. Problem 8 (10 points) Let A = {1, 2, 3} × {1, 2, 3}, and define Ｒ on A by (x_1, y_1)Ｒ(x_2, y_2) if x_1 + y_1 = x_2 + y_2 for (x_i, y_i) ∈ A. 1) (5 points) Show that Ｒ is an equivalence relation. 2) (5 points) Determine the partition of A induced by Ｒ. Ans: 1) For all (x, y) ∈ A, x + y = x + y so (x, y)Ｒ(x, y). For (x_i, y_i) ∈ A, (x_1, y_1)Ｒ(x_2, y_2) implies x_1 + y_1 = x_2 + y_2, which implies x_2 + y_2 = x_1 + y_1, so (x_2, y_2)Ｒ(x_1, y_1). (x_1, y_1)Ｒ(x_2, y_2) and (x_2, y_2)Ｒ(x_3, y_3) imply x_1 + y_1 = x_2 + y_2 and x_2 + y_2 = x_3 + y_3, which implies x_1 + y_1 = x_3 + y_3, so (x_1, y_1)Ｒ(x_3, y_3). Since Ｒ is reflexive, symmetric, and transitive, Ｒ is an equivalence relation. 2) A = {(1, 1)} ∪ {(1, 2), (2, 1)} ∪ {(1, 3), (2, 2), (3, 1)} ∪ {(1, 4), (2, 3), (3, 2), (4, 1)} ∪ {(3, 3)}. Problem 9 (10 points) Ｒ is said to be a tournament if Ｒ is irreflexive and for all x ≠ y, either (x, y) ∈ Ｒ or (y, x) ∈ Ｒ. Let Ｒ be a transitive tournament. 1) (5 points) Show that Ｒ has a maximal element. 2) (5 points) Show that Ｒ has a greatest element. Ans: 1) See p. 302 in the slides. 2) It suffices to show that Ｒ has only one maximal element. Assume that x and x' are maximal elements in Ｒ and x ≠ x'. For all a ∈ Ｒ, a ≠ x, (x, a) !∈ Ｒ. Since x' is one of a's, (x, x') !∈ Ｒ. Similarly, (x', x) !∈ Ｒ. This violates that for all x ≠ y, either (x, y) ∈ Ｒ or (y, x) ∈ Ｒ. So Ｒ has only one maximal element and the claim holds. (!∈: 不屬於) Problem 10 (10 points) Let S be a set with |S| = N, and c_1, c_2, …, c_t be conditions on the elements of |S|. N(abc…) denotes the number of elements of S that satisfy a Λ b Λ c Λ …. Then N(﹁c_1 ﹁c_2 … ﹁c_t) denotes the number of elements of S that satisfy none of the conditions c_i. Show that t k N(﹁c_1 ﹁c_2 … ﹁c_t) = Σ (-1) Σ N(c_i1 c_i2 … c_ik). k=0 1≦i1＜i2＜…＜ik≦t Ans: See pp. 366-367 in the slides. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.115.45.131 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1462037708.A.631.html ※ simonmao:轉錄至看板 b04902xxx 05/10 13:06