※ [本文转录自 NTU-Exam 看板 #1LkyI9mk ] 作者: rod24574575 (天然呆) 看板: NTU-Exam 标题: [试题] 103下 吕育道 离散数学 第一次期中考+解答 时间: Sat Aug 1 02:55:01 2015 课程名称︰离散数学 课程性质︰选修 课程教师：吕育道 开课学院：电资学院 开课系所︰资工系 考试日期（年月日）︰2015.04.09 考试时限（分钟）： 试题 : Discrete Mathematics Examination on April 9, 2015 Spring Semester, 2015 Problem 1 (10 points) Define the moves R: (x, y) → (x + 1, y) and U: (x, y) → (x, y + 1). In how may ways can one go from (1, 2) to (7, 8) without entering the half-plane y > x + 1? (It is fine if you provide a numerical expression without evaluating it.) Ans: 1 ╭ 12 ╮ b_6 =──│ │ = 132 7 ╰ 6 ╯ Problem 2 (10 points) How many integer solutions can satisfy the equation x_1 + x_2 + x_3 + x_4 = 15, where x_1 ≧ 1, x_2 ≧ 2, x_3 ≧ 3, x_4 ≧ 4. (It is fine if you provide a numerical expression without evaluating it.) Ans: Let y_1 = x_1 - 1, y_2 = x_2 - 2, y_3 = x_3 - 3, y_4 = x_4 - 4: The equation y_1 + y_2 + y_3 + y_4 = 5 can be obtained. There are C(8, 5) = 56 solutions. Problem 3 (10 points) Prove that for any n ∈ Z+, gcd(5n + 3, 7n + 4) = 1. Ans: For any n ∈ Z+, (5n + 3)(7) + (7n + 4)(-5) = (35n + 21) - (35n + 20) = 1. So, it follows that gcd(5n + 3, 7n + 4) = 1. Problem 4 (10 points) What is the coefficient of (x^12)(y^13) in the expansion of (3x + 2y)^25? (You do not need to evaluate the number numerically.) Ans: From the binomial theorem it follows that this coefficient is 12 13 ╭ 25 ╮ 12 13 25! 3 * 2 * │ │ = 3 * 2 * ──── ╰ 13 ╯ 13!12! Problem 5 (10 points) Let ψ = ((p Λ q) → r) <─> (p → (q → r)) be a Boolean expression. State which truth values for p, q and r will not satisfy ψ? Ans: None, because ψ is a tautology. Problem 6 (10 points) A triangular number T_n is a number that can be represented as an equilateral triangle of dots, as shown in the figure: n = 1 n = 2 n = 3 n = 4 n = 5 ˙ ˙ ˙˙ ˙ ˙˙ ˙˙˙ ˙ ˙˙ ˙˙˙ ˙˙˙˙ ˙ ˙˙ ˙˙˙ ˙˙˙˙ ˙˙˙˙˙ T_n = 1 T_n = 3 T_n = 6 T_n = 10 T_n = 15 Find the formula for the value of T_n + T_(n-1) for any n ≧ 2. Ans: First notice that T_n = 1 + 2 + 3 + … + n = n(n+1)/2, hence for n ≧ 2 n(n+1) (n-1)n n^2 + n + n^2 - n 2n^2 T_n + T_(n-1) = ──── + ──── = ────────── = ─── = n^2. 2 2 2 2 Problem 7 (10 points) Let α be any real number such that α + 1/α ∈ Z. Use induction to prove n 1 α + ─── ∈ Z, for all n ∈ N. α^n Ans: We proceed by induction over n. 1. For n = 0 and n = 1: For n = 0, α^0 + 1/(α^0) = 1 + 1 = 2 ∈ Z. Also note that, by assumption, α^1 + 1/(α^1) ∈ Z. 2. For n = k: Assume α^k + 1/(α^k) ∈ Z and α^(k-1) + 1/(α^(k-1)) ∈ Z. 3. For n = k + 1: Notice that k+1 1 α + ───── α^(k+1) ╭ 1 ╮╭ k 1 ╮ ╭ k-1 1 ╮ = │α + ──││α + ───│-│α + ─────│ ∈ Z ╰ α ╯╰ α^k ╯ ╰ α^(k-1) ╯ Hence α^(k+1) + 1/(α^(k+1)) ∈ Z Therefore we can infer that α^n + 1/(α^n) ∈ Z, for any n ∈ N. Problem 8 (10 points) Let A, B be two set with |A∩B| = 4, and |A∪B| = 9. (1) (5 points) How many C satisfy A∩B ⊆ C ⊆ A∪B? (2) (5 points) How many C satisfying (1) contain an even number of elements? Ans: 1) Since |A∪B| - |A∩B| = 5; there are 2^5 subsets C where A∩B ⊆ C ⊆ A∪B. 2) For the cases |C| = 4, 6, 8, the numbers containing an even number of ╭ 5 ╮ ╭ 5 ╮ ╭ 5 ╮ elements are │ │, │ │, and │ │, respectively. So the total ╰ 0 ╯ ╰ 2 ╯ ╰ 4 ╯ number is 16. Problem 9 (10 points) Recall that if f: A → B and A' ⊆ A, then f(A'), the image of A' under f, is defined as {f(a): a ∈ A'}. Assume A1, A2 ⊆ A. (1) (5 points) Prove f(A1∪A2) = f(A1)∪f(A2). (2) (5 points) Prove f(A1∩A2) = f(A1)∩f(A2) when f is one-to-one. Ans: (1) (Necessity) For each b ∈ f(A1∪A2), b = f(a) for some a ∈ A1∪A2. This implies that b = f(a) for some a ∈ A1 or f(a) = b for some a ∈ A2, and b = f(a) ∈ f(A1)∪f(A2). So f(A1∪A2) ⊆ f(A1)∪f(A2). (Sufficiency) For each b ∈ f(A1)∪f(A2), b = f(a) for some a ∈ A1 or f(a) = b for some a ∈ A2. This implies that b = f(a) for some a ∈ A1∪A2. So b = f(a) ∈ f(A1∪A2). (2) (Necessity) For each b ∈ f(A1∩A2), f(a) = b for some a ∈ A1∩A2. This implies that f(a) = b for some a ∈ A1 and f(a) = b for some a ∈ A2. So f(a) = b ∈ f(A1)∩f(A2) and f(A1∈A2) ⊆ f(A1)∩f(A2). (Sufficiency) For each b ∈ f(A1)∩f(A2), b = f(a) for some a1 ∈ A1 and b = f(a) for some a2 ∈ A2. Recall that f is one-to-one. So a1 = a2 ∈ A1∩A2. This implies that b = f(a) ∈ f(A1)∩f(A2) ⊆ f(A1∩A2). Problem 10 (10 points) Let A = {1, 2, 3, 4, 5}. Determine the number of bijective functions f: A → A which satisfy f(1) ≠ 1 and f(2) ≠ 2. Ans: It suffices to calculate the number of bijective functions which f(1) = 1 or f(2) = 2. So 5! - (4! + 4! - 3!) = 78. --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.162.254.199 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1438368905.A.C2E.html

※ 发信站: 批踢踢实业坊(ptt.cc) ※ 转录者: w4a2y4 (140.112.4.192), 03/14/2016 19:27:55