※ [本文轉錄自 NTU-Exam 看板 #1LlDCp_4 ]
作者: rod24574575 (天然呆) 看板: NTU-Exam
標題: [試題] 103下 呂育道 離散數學 第二次期中考+解答
時間: Sat Aug 1 22:09:52 2015
課程名稱︰離散數學
課程性質︰選修
課程教師：呂育道
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2015.05.21
考試時限（分鐘）：
試題 :
Discrete Mathematics
Examination on May 21, 2015
Spring Semester, 2015
Problem 1 (10 points)
Consider the poset
({{1}, {2}, {4}, {1, 2}, {1, 4}, {2, 4}, {3, 4}, {1, 3, 4}, {2, 3, 4}}, ⊆).
1. (3 points) Find the least upper bound of {{2}, {4}}, if it exists.
2. (3 points) Find all lower bounds of {{1, 3, 4}, {2, 3, 4}}.
3. (4 points) Find the greatest lower bound of {{1, 3, 4}, {2, 3, 4}}, if it
exists.
(Hint: Draw the directed graph for the poset.)
Ans:
1. {2, 4}.
2. {3, 4}, {4}.
3. {3, 4}.
Problem 2 (10 points)
Consider two relations represented by the following matrices:
┌ 1 0 1 ┐ ┌ 0 1 0 ┐
(5 points) 1. │ 0 1 0 │, (5 points) 2. │ 0 1 0 │.
└ 1 0 1 ┘ └ 0 1 0 ┘
Determine for each relation whether it is reflexive, irreflexive, symmetric,
antisymmetric, and/or transitive. Write down all labels that apply. Recall
that a relation R is antisymmetric if (x, y) ∈ R Λ (y, x) ∈ R => x = y
for all x, y ∈ A. (Points will be given only when you enumerate all and only
those apply.)
Ans:
1. Reflexive, symmetric, transitive.
2. Antisymmetric, transitive.
Problem 3 (10 points)
Find a formula for the convolution of the following two sequences,
{(-1)^n}_(n=0,1,2,…), {(-1)^n}_(n=0,1,2,…).
Ans:
See p.459 of the lecture notes. An alternative is to start from the definition
of the convolution with the above two sequences:
n k n-k n n n
Σ (-1) (-1) = Σ (-1) = (-1) (n+1).
k=0 k=0
Problem 4 (10 points)
Let n ∈ Z+ with n ≧ 2. Let ψ(n) stand for Euler's totient function, which
counts the number of positive integers smaller than n and are relative prime
to n.
1. (3 points) Determine ψ(2^n).
2. (3 points) Determine ψ(ψ(2^n)).
3. (4 points) Determine ψ((2p)^n) where p is an odd prime.
Ans:
1. ψ(2^n) = 2^n - 2^(n-1) = (2^(n-1))(2-1) = 2^(n-1).
2. ψ(ψ(2^n)) = ψ(2^(n-1)) = 2^(n-1) - 2^(n-2) = (2^(n-2))(2-1) = 2^(n-2).
3. ψ((2p)^n) = ψ((2^n)(p^n)) = ψ(2^n)ψ(p^n) = (2^(n-1))(p^n - p^(n-1))
= (2^(n-1))(p^(n-1))(p-1).
Problem 5 (10 points)
x^2
Determine the sequence whose generating function is f(x) = ─────
1 - x^3
Ans:
As
x^2 2 3 6 9 2 5 8 11
f(x) = ─────= x (1 + x + x + x + …) = x + x + x + x + … ,
1 - x^3
the sequence is 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, ….
Problem 6 (10 points)
Let n ≧ 1 be an odd number and A = {1, 2, …, n}. Let σ be a permutation
of A on itself (so σ(A) = A). Is the number
P = (1 - σ(1))(2 - σ(2))…(n - σ(n))
odd or even or sometimes odd and sometimes even? Justify your answer.
Ans:
P is even. Notice that for an odd n ≧ 1, in A there are (n-1)/2 even numbers
and (n-1)/2 + 1 odd numbers. By the Pigeonhole Principle, there is a least one
odd number k ≦ n such that σ(k) is odd, making (k - σ(k)) even and P even
as well.
Problem 7 (10 points)
Solve the following recurrence relations:
1) (5 points) a_n + 2·a_(n-1) + 2·a_(n-2) = 0 with a_0 = 1 and a_1 = 3.
2) (5 points) a_(n+2) = a_(n+1) a_n with a_0 = 1 and a_1 = 2. (Note that it
is acceptable if you express a_n in terms of well-known sequences.)
Ans:
1) (√2)^n (cos(3nπ/4) + 4·sin(3nπ/4)), n ≧ 0.
2) a_n = 2^(F_n), where F_n = F_(n-1) + F_(n-2) with F_0 = 0 and F_1 = 1.
Problem 8 (10 points)
Let f: A → B be invertible. Then it is known that there is a function
g: B → A such that g。f = 1_A and f。g = 1_B. Show that g is unique.
Ans:
See pp.286-287 of the lecture notes.
Problem 9 (10 points)
Suppose A = R^2. Define ￡ on A by (x1, y1)￡(x2, y2) if x1 = x2. Prove that
￡ is an equivalence relation on A.
Ans:
It suffices to verify the properties of reflexivity, symmetry, and
transitiveness. For all (x, y) ∈ A, it is obvious that (x, y)￡(x, y) since
x = x. So ￡ is reflexive. If (x1, y1), (x2; y2) ∈ A with (x1, y1)￡(x2, y2),
then x1 = x2. So, x2 = x1 and (x2, y2)￡(x1, y1). Hence ￡ is symmetric. Let
(x1, y1), (x2, y2) and (x3, y3) be in A with (x1, y1)￡(x2, y2) and
(x2, y2)￡(x3, y3). Then (x1, y1)￡(x2, y2) implies x1 = x2, and
(x2, y2)￡(x3, y3) implies x2 = x3. It follows that x1 = x3, so
(x1, y1)￡(x3, y3) and ￡ is transitive.
Problem 10 (10 points)
Consider x_1 + x_2 + x_3 + x_4 = 19. Determine the number of integer solutions
if 0 ≦ x_i ＜ 8 for all 1 ≦ i ≦ 4.
╭ n+r-1 ╮
(Hint: There are │ │ integer solutions to x_1 + x_2 + … + x_n = r,
╰ r ╯
x_i ≧ 0 for all 1 ≦ i ≦ n.)
Ans:
Let c_i denote the condition x_i ≧ 8 for all i. By the inclusion-exclusion
___ ___ ___ ___ ╭ 22 ╮ ╭ 4 ╮╭ 14 ╮ ╭ 4 ╮╭ 6 ╮
principle, N(c_1 c_2 c_3 c_4) = │ │ - │ ││ │ + │ ││ │.
╰ 19 ╯ ╰ 1 ╯╰ 11 ╯ ╰ 2 ╯╰ 3 ╯
Or you can use the generating function method on p.466 of the lecture notes.