※ [本文转录自 NTU-Exam 看板 #1LsNnsv6 ]
作者: rod24574575 (天然呆) 看板: NTU-Exam
标题: [试题] 102下 吕育道 离散数学 第二次期中考+解答
时间: Sun Aug 23 15:55:30 2015
课程名称︰离散数学
课程性质︰选修
课程教师：吕育道
开课学院：电资学院
开课系所︰资工系
考试日期（年月日）︰2014.05.08
考试时限（分钟）：
试题 :
Discrete Mathematics
Examination on May 8, 2014
Spring Semester, 2014
Note: You may use any results proved in the class unless stated otherwise.
Problem 1 (10 points)
Let A = {1, 2, 3, 4, 5}.
1) (5 points) How many bijective functions f: A → A satisfy f(1) ≠ 1?
2) (5 points) How many functions f: A → A are invertible?
Ans:
1) 4 * (4!) = 96.
2) 5! = 120.
Problem 2 (10 points)
How many monotone increasing functions from {1, 2, …, m} to {1, 2, …, n} are
there?
Ans:
╭ m+n-1 ╮
│ │, (see p.251 of the slides).
╰ m ╯
Problem 3 (10 points)
There are three kinds of books (e.g., novels, poems and biographies) on the
shelf. What is the minimum number of books we should pick up in order to
guarantee that either at least 5 novels or at least 4 poems or at least 7
biographies are picked up?
Ans:
By the pigeonhole principle, we should pick up at least 5 + 4 + 7 - 3 + 1 = 14
books.
Problem 4 (10 points)
Define N(abc...) as the number of elements in set S that satisfy
a Λ b Λ c Λ …. Denotes S_k = Σ N(c_i1 c_i2 … c_ik),
1≦i1≦i2＜…≦ik≦t
where c_1, …, c_t are the t conditions. Let E_m be the number of elements in
S that satisfy exactly m of the t conditions. Please express S_r in terms of
E_m for any r ≦ m.
Ans:
╭ m ╮
Since each element that satisfies exactly m conditions is counted │ │
times in S_r if m ≧ r, ╰ r ╯
t ╭ m ╮
S_r = Σ │ │E_m.
m=r ╰ r ╯
Problem 5 (10 points)
A derangement d_n is a permutation of 1, 2, …, n in which 1 is not in the
first place, 2 is not in the second place, etc. Show that
d_n = (n-1)(d_(n-1) + d(n-2)) for n ≧ 3.
Ans:
Recall that d_0 = 1. It is also clear that d_1 = 0 and d_2 = 1. Consider
derangements of 1, 2, …, n in which number m ≠ 1 is in the 1st position.
Among them, there are d_(n-1) derangements for which 1 does not occupy the
mth position. It is like considering the derangements of
1, 2, …, m-1, m+1, …, n
as 1 now has a forbidden position. Similarly, among them, there are d_(n-2)
derangements for which 1 occupies the mth position. It is like considering the
derangements of
2, …, m-1, m+1, …, n.
The equality follows by observing that there are n-1 choices for m.
Problem 6 (10 points)
For any choice of seven distinct numbers from {1, 2, …, 11}, show that there
must be at least two numbers which sum to 12.
Ans:
Let the pigeons be the seven numbers selected. Define six pigeonholes as the
following six sets: {1, 11}, {2, 10}, {3, 9}, {4, 8}, {5, 7}, and {6}. When
a number is selected, it gets placed into the pigeonhole corresponding to the
set that contains it. Since seven numbers are selected and placed in six
pigeonholes, some pigeonhole contains two numbers. So, the claim holds.
Problem 7 (10 points)
Suppose |A| = n.
1) (5 points) How many relations on A are there which are a total order?
2) (5 points) How many relations on A are there which are reflexive and
symmetric?
Ans:
1) n!.
2) For any (x, y) ∈ A and x ≠ y, the number of decisions to make for
╭ n ╮ (n^2 - n)
membership in R is │ │ =──────. Thus, there are 2^((n^2 - n) / 2)
╰ 2 ╯ 2
relations which are reflexive and symmetric.
Problem 8 (10 points)
Let A = {1, 2, 3} × {1, 2, 3}, and define R on A by (x_1, y_1)R(x_2, y_2) if
x_1 + y_1 = x_2 + y_2 for (x_i, y_i) ∈ A.
1) (5 points) Show that R is an equivalence relation.
2) (5 points) Determine the partition of A induced by R.
Ans:
1) For all (x, y) ∈ A, x + y = x + y so (x, y)R(x, y). For (x_i, y_i) ∈ A,
(x_1, y_1)R(x_2, y_2) implies x_1 + y_1 = x_2 + y_2, which implies
x_2 + y_2 = x_1 + y_1, so (x_2, y_2)R(x_1, y_1). (x_1, y_1)R(x_2, y_2) and
(x_2, y_2)R(x_3, y_3) imply x_1 + y_1 = x_2 + y_2 and x_2 + y_2 = x_3 + y_3,
which implies x_1 + y_1 = x_3 + y_3, so (x_1, y_1)R(x_3, y_3). Since R is
reflexive, symmetric, and transitive, R is an equivalence relation.
2) A = {(1, 1)} ∪ {(1, 2), (2, 1)} ∪ {(1, 3), (2, 2), (3, 1)} ∪
{(2, 3), (3, 2)} ∪ {(3, 3)}.
Problem 9 (10 points)
Let (A, R) be a finite poset.
1) (5 points) Prove that a greatest element, if it exists, must be a maximal
element.
2) (5 points) Prove that the greatest element, if it exists, must be the
only maximal element.
Ans:
1) Let x ∈ A be a greatest element. Then (y, x) ∈ R for all y ∈ A but
y ≠ x. Since (A, R) is antisymmetric, (x, y) 不属于 R. Thus x ∈ A is a
maximal element by definition.
2) It is known that greatest element is unique (see p. 370 in the slides). Let
x ∈ A be the greatest element and x' ≠ x ∈ A be a distinct maximal
element. Note that (x, y) 不属于 R for all y ∈ A but y ≠ x because x is
also a maximal element by (1). So we have (x, x') 不属于 R in particular.
By the same argument, (x', x) 不属于 R. This violates the antisymmetric
property. So such an x' does not exist.
Problem 10 (10 points)
Let (A, R) be a poset. Prove or disprove that there do not exist distinct
x_1, x_2, …, x_n ∈ A, n ≧ 2, such that
(x_1, x_2), (x_2, x_3), …, (x_(n-1), x_n), (x_n, x_1) ∈ R.
Ans:
See pp. 357ff in the slides.