課程名稱︰離散數學
課程性質︰選修
課程教師：呂育道
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2013.03.28
考試時限（分鐘）：
試題 :
Discrete Mathematics
Examination on March 28, 2013
Spring Semester, 2013
Note: You may use any results proved in the class unless stated otherwise.
Problem 1 (10 points)
Determine the coefficient of x^2 y z^2 in (x/2 + y - 3z)^5.
Ans: ╭ 5 ╮ 2 135
│ │(1/2) (-3) = ───
╰ 2,1,2 ╯ 2
Problem 2 (10 points)
Suppose that k and n are integers with 1 ≦ k ＜ n. Prove that
╭ n-1 ╮╭ n ╮╭ n+1 ╮ ╭ n-1 ╮╭ n ╮╭ n+1 ╮
│ ││ ││ │ = │ ││ ││ │
╰ k-1 ╯╰ k+1 ╯╰ k ╯ ╰ k ╯╰ k-1 ╯╰ k+1 ╯
Ans: ╭ n-1 ╮╭ n ╮╭ n+1 ╮
│ ││ ││ │
╰ k-1 ╯╰ k+1 ╯╰ k ╯
(n-1)! n! (n+1)!
= ─────── ──────── ───────
(k-1)!(n-k)! (k+1)!(n-k-1)! (k)!(n-k+1)!
(n-1)! n! (n+1)!
= ─────── ──────── ───────
(k)!(n-k-1)! (k-1)!(n-k+1)! (k+1)!(n-k)!
╭ n-1 ╮╭ n ╮╭ n+1 ╮
= │ ││ ││ │
╰ k ╯╰ k-1 ╯╰ k+1 ╯
Problem 3 (10 points)
Consider a boolean expression p → [q → (p Λ q)].
1) (5 points) Give the simplest equivalent statement without →.
2) (5 points) Is it a tautology?
Ans: 1) True.
2) Yes.
Problem 4 (10 points)
n
Show that Σ (i×i!) = (n+1)! - 1 by mathematical induction.
i=1
Ans: With n = 1, we find that 1 × 1! = (1+1)! - 1 = 1. Assume the statement
k k+1
is true for n = k, so Σ (i×i!) = (k+1)! - 1. Then Σ (i×i!) =
i=1 i=1
k+1
Σ (i×i!) + (k+1)×(k+1)! = (k+1)! - 1 + (k+1)×(k+1)! = (k+2)! - 1.
i=1
Problem 5 (10 points)
How many functions from {0, 1, 2} to {0, 1, 2, …, n}^m are there? (Do not
write something like x^a^b as it is ambiguous. Write x^(a^b) or (x^a)^b.)
Ans: ((n+1)^m)^3 or (n+1)^(3m).
Problem 6 (15 points)
Suppose that N is the set of all natural numbers. Let E = {2k│ k ∈ N} and
O = {2k + 1│ k ∈ N}. It is well-known that N = E ∪ O, and |N| = |E| = |O|.
Then |N| = |E| + |O| - |E ∩ O| = 2|N| because |E ∩ O| = |ψ| = 0. Thus
|N| = 0. What is wrong with the argument?
Ans: The arithmetic operations cannot be applied to infinite sets.
Problem 7 (15 points)
A set is closed under a particular operation if the result of the operation
is in the set. Let S be a set. Then a collection Σ of subsets of S is called
a σ-algebra if S ∈ Σ and Σ is closed under the operations of:
1) taking complements,
2) forming countable unions of elements of Σ,
3) forming countable intersections of elements of Σ.
Suppose S = {1, 2, 3}, find the largest Σ. (Please show the elements in Σ.)
Ans: Σ = 2^S = {ψ, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}}.
Problem 8 (20 points)
There are two candidates A and B in an election. Let a and b be positive
integers, a > b, such that A gets a votes and B gets b votes. In the voting
counting process, a total of a+b votes will be announced sequentially such as
"A A B B A A B …". Call a vote announcing sequence legal if A's accumulated
vote count is greater than B's vote count throughout. For example, the above
sequence is not legal because after the 4th vote is announced, A ties with B.
1) (5 points) What is the total number of possible vote announcing sequences
(legal or otherwise)?
╭ a + b - 1 ╮
2) (5 points) Show that the number of illegal sequences is │ │
╰ a ╯
given that the first announced vote is for B.
╭ a + b - 1 ╮
3) (5 points) Show that the number of illegal sequences is │ │
╰ a ╯
given that the first announced vote is for A. (Hint: there must be a tie
and recall the reflection principle.)
4) (5 points) Finally, show that the total number of legal sequences is
a - b ╭ a + b ╮
────│ │.
a + b ╰ a ╯
Ans: Let T_A be the number of illegal sequences in which the first announced
vote is for A (so it must reach a tie with B in the counting of the votes)
and T_B be the number of illegal sequences in which the first announced
vote is for B.
╭ a + b ╮
1) The total number of sequences is │ │ by permuting
╰ a ╯
a As and b Bs.
╭ a + b - 1 ╮
2) T_B = │ │ because the remaining a + b - 1 votes can be
╰ a ╯
arbitrarily permuted.
3) For each illegal sequence, we reverse the votes up to the point of
the first tie to obtain a sequence that begins with the first
announced vote being for B. The mapping can be seen to be one-to-one.
So T_A = T_B.
╭ a + b ╮ a - b ╭ a + b ╮
4) │ │ - 2 T_A = ────│ │.
╰ a ╯ a + b ╰ a ╯