課程名稱︰離散數學
課程性質︰選修
課程教師：呂育道
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2016.03.31
考試時限（分鐘）：
試題 :
Discrete Mathematics
Examination on March 31, 2016
Spring Semester, 2016
Problem 1 (10 points)
How many antisymmetric relations can be formed over A = {1, 2, 3, 4, 5}?
Ans: Because |A| = 5, then there are
5 (5^2 - 5)/2 5 10
2 × 3 = 2 × 3
antisymmetric relations.
Problem 2 (10 points)
What is the coefficient of the term x^9 y^7 in the expansion of (5x - 2y)^16?
(You do not need to evaluate the number numerically.)
Ans: From the binomial theorem it follows that this coefficient is
9 7 ╭ 16 ╮ 9 7 ╭ 16 ╮ ╭ 9 7 16! ╮
5 * (-2) * │ │ = 5 * (-2) * │ │ = -│ 5 * 2 * ───│
╰ 9 ╯ ╰ 7 ╯ ╰ 9!7! ╯
Problem 3 (10 points)
Determine if the following functions are one-to-one or not. (Answers without
explanation get 0 points):
1. g = {(-1, 2), (0, 4), (2, -4), (5, 6), (10, 0)}.
2. f(x) = -x^3 + 3x^2 - 2.
Ans: 1. Consider any two different values in the domain of function g and
check that their corresponding outputs are different. Hence
function g is a one-to-one function.
2. f has three different zeros: x = 1, x = 1 ± √3; hence f is not a
one-to-one function.
Problem 4 (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 2
T_n + T_(n-1) = ──── + ──── = ────────── = ─── = n .
2 2 2 2
Problem 5 (10 points)
Let ψ = ﹁p → (q → r) <─> q → (p Ｖ r) be a Boolean expression. Write
down the truth table for ψ.
Ans: We have that
┌─┬─┬─┬──┬──┬──────┬──┬─────┬───────┐
│ p│ q│ r│ ﹁p│q→r│﹁p →(q→r)│pＶr│q →(pＶr)│﹁p → (q→r) │
│ │ │ │ │ │ │ │ │<─> q→(pＶr)│
├─┼─┼─┼──┼──┼──────┼──┼─────┼───────┤
│ 0│ 0│ 0│ 1 │ 1 │ 1 │ 0 │ 1 │ 1 │
│ 0│ 0│ 1│ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │
│ 0│ 1│ 0│ 1 │ 0 │ 0 │ 0 │ 0 │ 1 │
│ 0│ 1│ 1│ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │
│ 1│ 0│ 0│ 0 │ 1 │ 1 │ 1 │ 1 │ 1 │
│ 1│ 0│ 1│ 0 │ 1 │ 1 │ 1 │ 1 │ 1 │
│ 1│ 1│ 0│ 0 │ 0 │ 1 │ 1 │ 1 │ 1 │
│ 1│ 1│ 1│ 0 │ 1 │ 1 │ 1 │ 1 │ 1 │
└─┴─┴─┴──┴──┴──────┴──┴─────┴───────┘
ψ is a tautology, hence any value of p, q and r will satisfy ψ.
Problem 6 (10 points)
Determine |A ∪ B ∪ C|, when |A| = 10, |B| = 100 and |C| = 1000 and
1. (5 points) Case 1: A ∩ B = A ∩ C = B ∩ C = ψ.
2. (5 points) Case 2: A ⊆ B ⊆ C.
Ans: We know that |A ∪ B ∪ C| = |A| + |B| + |C| - (|A ∩ B| + |A ∩ C| +
|B ∩ C|) + |A ∩ B ∩ C|.
1. Case 1: |A ∪ B ∪ C| = (10 + 100 + 1000) - (0 + 0 + 0) + 0 = 1110.
2. Case 2: If A ⊆ B ⊆ C, then |A ∩ B| = |A|, |A ∩ C| = |A|,
|B ∩ C| = |B| and |A ∩ B ∩ C| = |A|. Hence
|A ∪ B ∪ C| = (10 + 100 + 1000) - (10 + 100 + 10) + 10
= 1000.
Problem 7 (10 points)
Let F_n be the n-th Fibonacci number (F_0 = 0, F_1 = 1).
Prove by induction that
F_1 + F_2 + … + F_n = F_(n+2) - 1, n ≧ 1.
Ans: We proceed by induction over n:
1. For n = 1: Note that F_1 = 1 = 2 - 1 = F_3 - 1, so the property holds
for n = 1.
2. For n = k: Now, for n = k, we suppose that the property
F_1 + F_2 + … + F_n = F_(n+2) - 1 holds.
3. For n = k + 1: For n = k + 1, we have that
F_1 + F_2 + … + F_k + F_(k+1)
= (F_1 + F_2 + … + F_k) + F_(k+1)
= F_(k+2) - 1 + F_(k+1)
= F_(k+3) - 1
= F_((k+1)+2) - 1,
so the property also holds for n = k + 1.
Problem 8 (10 points)
In the sequence 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, … each term starting from
the third is the sum of the two preceding terms, but addition is done mod 10.
Prove that the sequence is purely periodic.
Ans: Any two consecutive terms determine all the succeeding terms and also
all the preceding terms. Thus the sequence will be periodic if any pair
(a, b) of successive terms repeats. Consider 101 successive terms
1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, …. They form 100 pairs: (1, 1), (1, 2),
(2, 3), (3, 5), …. Because all the numbers are between 0 and 9, we have
at most 100 possible distinct pairs. Since the pair (0, 0) cannot occur,
then there are only 99 distinct pairs, so from the 100 pairs we
considered, by the Pigeonhole principle at least 2 will repeat, so the
sequence is periodic.
Problem 9 (10 points)
How many integer solutions are there for the following inequality?
x_1 + x_2 + … + x_7 ≦ 20,
where x_i ≧ 1 for 1 ≦ i ≦ 7.
Ans: The solution is equivalent to the solution of
x_1 + x_2 + … + x_7 ≦ 20 - 7 = 13,
where x_i ≧ 0 for 1 ≦ i ≦ 7.
which is also equivalent to the solution of
x_1 + x_2 + … + x_7 + x_8 = 13,
where x_i ≧ 0 for 1 ≦ i ≦ 8.
Therefore, the number of the integer solutions of the original inequality
is
╭ (7 + 1) + 13 - 1 ╮ ╭ 20 ╮
│ │ = │ │
╰ 13 ╯ ╰ 13 ╯
Problem 10 (10 points)
There are 6 jobs (numbered 1 to 6) and 4 employees (numbered 1 to 4). Each job
is only assigned to some employee so that each employee is assigned at least
one job. Finally, job 1 is given to employee 1. How many valid job assignments
are there?
Ans: onto(5, 3) + onto(5, 4)
3 k╭ 3 ╮ 5 4 k╭ 4 ╮ 5
= Σ (-1) │ │(3 - k) + Σ (-1) │ │(4 - k)
k=0 ╰ k ╯ k=0 ╰ k ╯
= 390