※ [本文转录自 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/cn.aspx?n=bbs/NTU-Exam/M.1440316534.A.E46.html

※ 发信站: 批踢踢实业坊(ptt.cc) ※ 转录者: simonmao (140.112.16.145), 04/29/2016 14:28:42