課程名稱︰離散數學
課程性質︰選修
課程教師：呂育道
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰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.