課程名稱︰離散數學 課程性質︰選修 課程教師：呂育道 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰2014.06.19 考試時限（分鐘）： 試題 : Discrete Mathematics Examination on June 19, 2014 Spring Semester, 2014 Note: You may use any results proved in the class unless stated otherwise. Problem 1 (10 points) Determine the sequence generated by the following generating functions: 1) (5 points) 1 / (3 - x) 2) (5 points) x / (1 - x)^2 Ans: 1) 1, 1/3, (1/3)^2, … 2) See p. 452 of the slides. Problem 2 (10 points) Solve the following recurrence relations: 1) (5 points) a_(n+2) = a_(n+1) + a_n, a_0 = 1, a_1 = 1/2. 2) (5 points) a_n + 2a_(n-1) + 2a_(n-2) = 0, n ≧ 2, a_0 = 1, a_1 = 3. Ans: 1 ╭╭ 1 + √5 ╮n ╭ 1 - √5 ╮n ╮ 1) a_n =──││──── │ + │──── │ │. (The steps are similar to 2 ╰╰ 2 ╯ ╰ 2 ╯ ╯ pp. 531-533 of the slides.) n ╭ 3nπ ╮ ╭ 3nπ ╮ 2) a_n = (√2) (cos│───│ + 4sin│───│). (The steps are similar to ╰ 4 ╯ ╰ 4 ╯ pp. 553-554 of the slides.) Problem 3 (10 points) Solve the recurrence relation a_n - 3a_(n-1) = n with a_0 = 1 by the generating function method. Ans: See pp. 588-591 of the slides. Problem 4 (10 points) 1 + √(1 + 8 * |E|) Let G = (V, E) be an undirected graph. Show that |V| ≧ ─────────── 2 Ans: See p. 621 of the slides. Problem 5 (10 points) Let G = (V1, V2, E) be a connected bipartite undirected graph. Show that if |V1| ≠ |V2|, then G has no Hamiltonian cycles. Ans: The nodes on a Hamiltonian cycle in G must alternate between nodes in V1 and those in V2 as G is bipartite. As the cycle must exhaust all nodes, |V1| = |V2|. Problem 6 (10 points) Let T = (V, E) be a tree. Show that T is planar. Ans: See p. 696 of the slides. Problem 7 (10 points) Let T = (V, E) be a rooted binary tree and |V| = n. 1) (5 points) Determine the maximum height that T can attain. 2) (5 points) If T is complete and n is odd, what is the maximum height that T can attain? Ans: 1) n - 1 2) (n - 1) / 2 Problem 8 (10 points) Let (R, +, ·) be a ring. Show that a unit in a ring R cannot be a proper divisor of zero. (Recall that if there exists z ∈ R such that z + a = a + z = a for every a ∈ R, then z is called a zero. Note that such z is unique. For any a ∈ R, if there is one element b ∈ R where a·b = z or b·a = z, then a is called a proper divisor of zero. For any a ∈ R, if there is an element u ∈ R such that a·u = u·a = a, then u is called a unit.) Ans: See p. 725 of the slides. Problem 9 (10 points) Let n be any positive integer. Show that the congruence modulo n is an equivalence relation on Z. (Recall that a relation is an equivalence one if it is reflexive, symmetric and transitive.) Ans: It suffices to verify the reflexive, symmetric, and transitive properties. Let a, b, c ∈ Z. 1) (Reflexivity) a - a = 0 and n divides 0, so a ≡ a mod n. 2) (Symmetry) Let a ≡ b mod n. Then a - b = kn for some integer k. b - a = -(a - b) = -kn, so n divides b - a and b ≡ a mod n. 1) (Transitivity) Let a ≡ b mod n and b ≡ c mod n. Then a - b = kn and b - c = k'n for some integers k, k'. So, a - c = (k + k')n and a ≡ c mod n. Problem 10 (10 points) Show that every group of prime order is cyclic. Ans: Pick any element a ≠ e of the group G. Note that o(a) > 1. As o(a) divides |G|, a prime number, o(a) = |G|. This implies that every b ∈ G must be of the form a^k for some k ∈ Z. --

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