※ [本文轉錄自 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.