課程名稱︰離散數學 課程性質︰選修 課程教師：呂育道 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰2015.06.25 考試時限（分鐘）： 試題 : Discrete Mathematics Examination on June 25, 2015 Problem 1 (10 points) Show that every group of prime order is cyclic. Ans: Let G be a group of prime order p and let a ≠ e be an element in G. Because a ≠ e, 1 < o(a). By the Lagrange Theorem, we know that o(a) divides |G| which is a prime, hence o(a) = p. This implies that a generates G, i.e., G is cyclic. Problem 2 (10 points) Calculate 6^(-1) mod 13. Ans: We know that 6^(-1) exists in (Z_13, ×) because gcd(6, 13) = 1. By brute force we have: 6 × 0 ≡ 0(mod 13) ; 6 × 6 ≡ 10(mod 13) 6 × 1 ≡ 6(mod 13) ; 6 × 7 ≡ 3(mod 13) 6 × 2 ≡ 12(mod 13) ; 6 × 8 ≡ 9(mod 13) 6 × 3 ≡ 5(mod 13) ; 6 × 9 ≡ 2(mod 13) 6 × 4 ≡ 11(mod 13) ; 6 × 10 ≡ 8(mod 13) 6 × 5 ≡ 4(mod 13) ; 6 × 11 ≡ 1(mod 13) So 6^(-1) ≡ 11(mod 13). Alternatively, use the Extended Euclidean Algorithm: 13 = 6 * 2 + 1 ╮ > => gcd(13, 6) = 1. 6 = 1 * 6 ╯ From this we get 1 = 13 - 6 * 2 ╮ > => gcd(13, 6) = 1 = 13 + 6(-2). 1 = 13 + 6(-2) ╯ hence 6^(-1) ≡ -2 ≡ 11(mod 13). Problem 3 (10 points) Which of the following are groups? 1. (Z_10, +). 2. (Z*_12, +). 3. (Z_14, ×). 4. (Z*_15, ×). 5. (Z8, -). In the case of non-groups, provide a reason. Ans: 1. (Z_10, +) is a group. 2. (Z*_12, +) is not a group because + is not closed modulo 12. 3. (Z_14, ×) is not a group because some elements have no inverses. 4. (Z*_15, ×) is a group. 5. (Z8, -) is not a group because it fails the associativity property. Problem 4 (10 points) Let G = (V, E) be a loop-free connected undirected graph with |V| ≧ 2. Prove that G contains at least two vertices v and w, where deg(v) = deg(w). Ans: Since G is loop-free and connected, we have 1 ≦ deg(x) ≦ n-1 for all x ∈ V. By the pigeonhole principle, at least two of n vertices have the same degree. Problem 5 (10 points) Let G = (V, E) be a loop-free connected planar graph with |V| = v and |E| = e > 2. Prove that e ≦ 3v-6. (Hint: Euler's Theorem says that v - e + r = 2 where r is the number of regions in the plane determined by a planar embedding of G.) Ans: See p. 646 of the slides. Problem 6 (10 points) Let T = (V, E) be a tree. 1) (5 points) Argue that T is planar. 2) (5 points) Assume that |V| = n. What is the sum of the degrees of all the vertices in T expressed as a function of n only? Ans: 1) By definition, every tree has no cycle. Thus it cannot contain a subgraph homo-morphic to either K_(3,3) or K_5. By Kuratowski's theorem, the claim holds. Or one can embed a tree on a plane level by level without edge crossing. 2) Σ deg(v) = 2|E| = 2(|V| - 1) = 2n - 2. v∈V Problem 7 (10 points) Consider a full m-ary tree with height h and v vertices. Determine h in terms of m and v. (Recall that a complete m-ary tree of height h is called a full m-ary tree if all the leaves are at level h.) Ans: As v = 1 + m + m^2 + ... + m^h = (m^(h+1) - 1) / (m - 1) , we have v(m-1) + 1 = m^(h+1). Consequently, h = log_m(v(m-1) + 1) - 1. Problem 8 (10 points) Let G1 and G2 be two subgroups of a group G = (G, 。). Show that G1∩G2 is also a subgroup of G. (Hint: It suffices to verify the closure and inverse properties.) Ans: By Theorem 105 (see p. 757 of the slides), it suffices to show the closure and inverse properties. 1) (Closure) Let x, y ∈ G1∩G2. Then x。y ∈ G1 and x。y ∈ G2, so x。y ∈ G1∩G2. 2) (Inverse) Let x ∈ G1∩G2. Then x^(-1) ∈ G1 and x^(-1) ∈ G2, so x^(-1) ∈ G1∩G2. Thus G1∩G2 is a subgroup of G. Problem 9 (10 points) Show that x^2 + x + 1 is irreducible over Z_2[x]. Ans: Since x 不整除 (x^2 + x + 1) and (x + 1) 不整除 (x^2 + x + 1), x^2 + x + 1 is irreducible. Problem 10 (10 points) Solve the recurrence relation a_n + 3a_(n-1) + 2a_(n-2) = 3^n, where a_0 = 0 and a_1 = 1. Ans: a_n = (-5/4)(-1)^n + (4/5)(-2)^n + (9/20)3^n, n ≧ 0. --

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