※ [本文轉錄自 NTU-Exam 看板 #1LsNnsv6 ] 作者: rod24574575 (天然呆) 看板: NTU-Exam 標題: [試題] 102下 呂育道 離散數學 第二次期中考+解答 時間: Sun Aug 23 15:55:30 2015 課程名稱︰離散數學 課程性質︰選修 課程教師：呂育道 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰2014.05.08 考試時限（分鐘）： 試題 : Discrete Mathematics Examination on May 8, 2014 Spring Semester, 2014 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) How many monotone increasing functions from {1, 2, …, m} to {1, 2, …, n} are there? Ans: ╭ m+n-1 ╮ │ │, (see p.251 of the slides). ╰ m ╯ Problem 3 (10 points) There are three kinds of books (e.g., novels, poems and biographies) on the shelf. What is the minimum number of books we should pick up in order to guarantee that either at least 5 novels or at least 4 poems or at least 7 biographies are picked up? Ans: By the pigeonhole principle, we should pick up at least 5 + 4 + 7 - 3 + 1 = 14 books. Problem 4 (10 points) Define N(abc...) as the number of elements in set S that satisfy a Λ b Λ c Λ …. Denotes S_k = Σ N(c_i1 c_i2 … c_ik), 1≦i1≦i2＜…≦ik≦t where c_1, …, c_t are the t conditions. Let E_m be the number of elements in S that satisfy exactly m of the t conditions. Please express S_r in terms of E_m for any r ≦ m. Ans: ╭ m ╮ Since each element that satisfies exactly m conditions is counted │ │ times in S_r if m ≧ r, ╰ r ╯ t ╭ m ╮ S_r = Σ │ │E_m. m=r ╰ r ╯ Problem 5 (10 points) A derangement d_n is a permutation of 1, 2, …, n in which 1 is not in the first place, 2 is not in the second place, etc. Show that d_n = (n-1)(d_(n-1) + d(n-2)) for n ≧ 3. Ans: Recall that d_0 = 1. It is also clear that d_1 = 0 and d_2 = 1. Consider derangements of 1, 2, …, n in which number m ≠ 1 is in the 1st position. Among them, there are d_(n-1) derangements for which 1 does not occupy the mth position. It is like considering the derangements of 1, 2, …, m-1, m+1, …, n as 1 now has a forbidden position. Similarly, among them, there are d_(n-2) derangements for which 1 occupies the mth position. It is like considering the derangements of 2, …, m-1, m+1, …, n. The equality follows by observing that there are n-1 choices for m. Problem 6 (10 points) For any choice of seven distinct numbers from {1, 2, …, 11}, show that there must be at least two numbers which sum to 12. Ans: Let the pigeons be the seven numbers selected. Define six pigeonholes as the following six sets: {1, 11}, {2, 10}, {3, 9}, {4, 8}, {5, 7}, and {6}. When a number is selected, it gets placed into the pigeonhole corresponding to the set that contains it. Since seven numbers are selected and placed in six pigeonholes, some pigeonhole contains two numbers. So, the claim holds. Problem 7 (10 points) Suppose |A| = n. 1) (5 points) How many relations on A are there which are a total order? 2) (5 points) How many relations on A are there which are reflexive and symmetric? Ans: 1) n!. 2) For any (x, y) ∈ A and x ≠ y, the number of decisions to make for ╭ n ╮ (n^2 - n) membership in R is │ │ =──────. Thus, there are 2^((n^2 - n) / 2) ╰ 2 ╯ 2 relations which are reflexive and symmetric. Problem 8 (10 points) Let A = {1, 2, 3} × {1, 2, 3}, and define R on A by (x_1, y_1)R(x_2, y_2) if x_1 + y_1 = x_2 + y_2 for (x_i, y_i) ∈ A. 1) (5 points) Show that R is an equivalence relation. 2) (5 points) Determine the partition of A induced by R. Ans: 1) For all (x, y) ∈ A, x + y = x + y so (x, y)R(x, y). For (x_i, y_i) ∈ A, (x_1, y_1)R(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)R(x_1, y_1). (x_1, y_1)R(x_2, y_2) and (x_2, y_2)R(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)R(x_3, y_3). Since R is reflexive, symmetric, and transitive, R is an equivalence relation. 2) A = {(1, 1)} ∪ {(1, 2), (2, 1)} ∪ {(1, 3), (2, 2), (3, 1)} ∪ {(2, 3), (3, 2)} ∪ {(3, 3)}. Problem 9 (10 points) Let (A, R) be a finite poset. 1) (5 points) Prove that a greatest element, if it exists, must be a maximal element. 2) (5 points) Prove that the greatest element, if it exists, must be the only maximal element. Ans: 1) Let x ∈ A be a greatest element. Then (y, x) ∈ R for all y ∈ A but y ≠ x. Since (A, R) is antisymmetric, (x, y) 不屬於 R. Thus x ∈ A is a maximal element by definition. 2) It is known that greatest element is unique (see p. 370 in the slides). Let x ∈ A be the greatest element and x' ≠ x ∈ A be a distinct maximal element. Note that (x, y) 不屬於 R for all y ∈ A but y ≠ x because x is also a maximal element by (1). So we have (x, x') 不屬於 R in particular. By the same argument, (x', x) 不屬於 R. This violates the antisymmetric property. So such an x' does not exist. Problem 10 (10 points) Let (A, R) be a poset. Prove or disprove that there do not exist distinct x_1, x_2, …, x_n ∈ A, n ≧ 2, such that (x_1, x_2), (x_2, x_3), …, (x_(n-1), x_n), (x_n, x_1) ∈ R. Ans: See pp. 357ff in the slides. --

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

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