作者simonmao (哈哈哈)
看板b04902xxx
標題Fw: [試題] 101下 呂育道 離散數學 第二次期中考+解答
時間Tue May 10 13:06:56 2016
※ [本文轉錄自 NTU-Exam 看板 #1N9EpCOn ]
作者: rod24574575 (天然呆) 看板: NTU-Exam
標題: [試題] 101下 呂育道 離散數學 第二次期中考+解答
時間: Sun May 1 01:35:04 2016
課程名稱︰離散數學
課程性質︰選修
課程教師:呂育道
開課學院:電資學院
開課系所︰資工系
考試日期(年月日)︰2013.05.09
考試時限(分鐘):
試題 :
Discrete Mathematics
Examination on May 9, 2013
Spring Semester, 2013
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)
x^3
Determine the sequence generated by f(x) = ─────.
1 - x^2
x^3
Ans: As f(x) = ───── = (x^3) (1 + x^2 + x^4 + …) = x^3 + x^5 + x^9 + …,
1 - x^2
f(x) generates the sequence {0, 0, 0, 1, 0, 1, 0, …}.
Problem 3 (10 points)
Suppose that n, r ∈ Z+ and 0 < r ≦ n. Prove that
╭ -n ╮ r╭ n + r - 1 ╮
│ │ = (-1) │ │.
╰ r ╯ ╰ r ╯
Ans: See p. 451 of the slides.
Problem 4 (10 points)
Find the generating function and pinpoint the coefficient for the number
of integer solutions to the equation c_1 + c_2 + c_3 + c_4 = 10 where
c_1 ≧ -3, c_2 ≧ -4, -5 ≦ c_3 ≦ 5, and c_4 ≧ 0. (There is no need to
calculate the numerical value of the coefficient. You only have to answer like
"the coefficient of x_i (you specify i) in the generating function … (you
write down the function).")
Ans: Let x_1 = c_1 + 3, x_2 = c_2 + 4, x_3 = c_3 + 5, and x_4 = c4, then the
original problem is equivalent to x_1 + x_2 + x_3 + x_4 = 22 where
x_1, x_2, x_4 ≧ 0, and 0 ≦ x_3 ≦ 10. Consequently, the answer is the
coefficient of x^22 in the generating function
(1 + x + x^2 + …)^3 (1 + x + x^2 + … + x^10).
Problem 5 (10 points)
Let n ∈ Z+.
1) (5 points) Determine ψ(2^n).
2) (5 points) Determine ψ((2^n)p) where p is an odd prime.
Ans: 1) ψ(2^n) = 2^n × (1 - 1/2) = 2^(n-1).
2) ψ((2^n)p) = (2^n)p × (1 - 1/2) × (1 - 1/p) = (2^(n-1))(p-1).
Problem 6 (10 points)
Assume that 11 integers are selected from S = {1, 2, 3, …, 100}. Show that
there are at least two, say x and y, such that 0 < |√x - √y| < 1. (Hint:
You may consider the pigeonhole principle and for any t ∈ S, 0 < √t < 10.)
Ans: For any t ∈ S, 0 < √t < 10, so there must be two integers x and y such
that floor(√x) = floor(√y). Thus, the claim holds.
Problem 7 (10 points)
Suppose |A| = m. How many relations on A are there which are irreflexive and
symmetric?
Ans: For any (x, y) ∈ A and x ≠ y, the number of decisions to make for
╭ m ╮ (m^2 - m) ((m^2 - m)/2)
membership in R is │ │ = ──────. Thus, there are 2
╰ 2 ╯ 2
relations which are irreflexive 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)} ∪
{(1, 4), (2, 3), (3, 2), (4, 1)} ∪ {(3, 3)}.
Problem 9 (10 points)
R is said to be a tournament if R is irreflexive and for all x ≠ y, either
(x, y) ∈ R or (y, x) ∈ R. Let R be a transitive tournament.
1) (5 points) Show that R has a maximal element.
2) (5 points) Show that R has a greatest element.
Ans: 1) See p. 302 in the slides.
2) It suffices to show that R has only one maximal element. Assume that
x and x' are maximal elements in R and x ≠ x'. For all a ∈ R,
a ≠ x, (x, a) !∈ R. Since x' is one of a's, (x, x') !∈ R.
Similarly, (x', x) !∈ R. This violates that for all x ≠ y, either
(x, y) ∈ R or (y, x) ∈ R. So R has only one maximal element and
the claim holds. (!∈: 不屬於)
Problem 10 (10 points)
Let S be a set with |S| = N, and c_1, c_2, …, c_t be conditions on the
elements of |S|. N(abc…) denotes the number of elements of S that satisfy
a Λ b Λ c Λ …. Then N(﹁c_1 ﹁c_2 … ﹁c_t) denotes the number of elements
of S that satisfy none of the conditions c_i. Show that
t k
N(﹁c_1 ﹁c_2 … ﹁c_t) = Σ (-1) Σ N(c_i1 c_i2 … c_ik).
k=0 1≦i1<i2<…<ik≦t
Ans: See pp. 366-367 in the slides.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.115.45.131
※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1462037708.A.631.html
1F:→ rod24574575 : 已收資訊系! 05/01 01:37
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: simonmao (140.112.16.145), 05/10/2016 13:06:56
2F:→ simonmao: 洗 05/10 23:20
3F:→ simonmao: 洗 05/10 23:21
4F:→ simonmao: 洗 05/10 23:21
5F:→ simonmao: 洗 05/10 23:21
6F:→ simonmao: 洗 05/10 23:21
7F:→ simonmao: 洗 05/10 23:21
8F:→ simonmao: 洗 05/10 23:21
9F:→ simonmao: 洗 05/10 23:21
10F:→ simonmao: 洗 05/10 23:21
11F:→ simonmao: 洗 05/10 23:21
12F:→ simonmao: 洗 05/10 23:21
13F:→ simonmao: 洗 05/10 23:21
14F:→ simonmao: 洗 05/10 23:21
15F:→ simonmao: 洗 05/10 23:21
16F:→ simonmao: 洗 05/10 23:21
17F:→ simonmao: 洗 05/10 23:21
18F:→ simonmao: 洗 05/10 23:21
19F:→ simonmao: 洗 05/10 23:21
20F:→ simonmao: 洗 05/10 23:21
21F:→ simonmao: 洗 05/10 23:21
22F:→ simonmao: 洗 05/10 23:21
23F:→ simonmao: 洗 05/10 23:21
24F:→ simonmao: 洗 05/10 23:21
25F:→ simonmao: 洗 05/10 23:21
26F:→ simonmao: 洗 05/10 23:21
27F:→ simonmao: 洗 05/10 23:21
28F:→ simonmao: 洗 05/10 23:21
29F:→ simonmao: 洗 05/10 23:21
30F:→ simonmao: 洗 05/10 23:21
31F:→ simonmao: 洗 05/10 23:21
32F:→ simonmao: 洗 05/10 23:21
33F:→ simonmao: 洗 05/10 23:21
34F:→ simonmao: 洗 05/10 23:21
35F:→ simonmao: 洗 05/10 23:21
36F:→ simonmao: 洗 05/10 23:21
37F:→ simonmao: 洗 05/10 23:21
38F:→ simonmao: 洗 05/10 23:21
39F:→ simonmao: 洗 05/10 23:21
40F:→ simonmao: 洗 05/10 23:21
41F:→ simonmao: 洗 05/10 23:21
42F:→ simonmao: 洗 05/10 23:21
43F:→ simonmao: 洗 05/10 23:21
44F:→ simonmao: 洗 05/10 23:21
45F:→ simonmao: 洗 05/10 23:21
46F:→ simonmao: 洗 05/10 23:21
47F:→ simonmao: 洗 05/10 23:21
48F:→ simonmao: 洗 05/10 23:21
49F:→ simonmao: 洗 05/10 23:21
50F:→ simonmao: 洗 05/10 23:21
51F:→ simonmao: 洗 05/10 23:21
52F:→ simonmao: 洗 05/10 23:21
53F:→ simonmao: 洗 05/10 23:21
54F:→ simonmao: 洗 05/10 23:21
55F:→ simonmao: 洗 05/10 23:21
56F:→ simonmao: 洗 05/10 23:21
57F:→ simonmao: 洗 05/10 23:21
58F:→ simonmao: 洗 05/10 23:21
59F:→ simonmao: 洗 05/10 23:21
60F:→ simonmao: 洗 05/10 23:21
61F:→ simonmao: 洗 05/10 23:21
62F:→ simonmao: 洗 05/10 23:22
63F:→ simonmao: 洗 05/10 23:22
64F:→ simonmao: 洗 05/10 23:22
65F:→ simonmao: 洗 05/10 23:22
66F:→ simonmao: 洗 05/10 23:22
67F:→ simonmao: 洗 05/10 23:22
68F:→ simonmao: 洗 05/10 23:22
69F:→ simonmao: 洗 05/10 23:22
70F:→ simonmao: 洗 05/10 23:22
71F:→ simonmao: 洗 05/10 23:22
72F:→ simonmao: 洗 05/10 23:22
73F:→ simonmao: 洗 05/10 23:22
74F:→ simonmao: 洗 05/10 23:22
75F:→ simonmao: 洗 05/10 23:22
76F:→ simonmao: 洗 05/10 23:22
77F:→ simonmao: 洗 05/10 23:22
78F:→ simonmao: 洗 05/10 23:22
79F:→ simonmao: 洗 05/10 23:22
80F:→ simonmao: 洗 05/10 23:22
81F:→ simonmao: 洗 05/10 23:22
82F:→ simonmao: 洗 05/10 23:22
83F:→ simonmao: 洗 05/10 23:22
84F:→ simonmao: 洗 05/10 23:22
85F:→ simonmao: 洗 05/10 23:22
86F:→ simonmao: 洗 05/10 23:22
87F:→ simonmao: 洗 05/10 23:22
88F:→ simonmao: 洗 05/10 23:22
89F:→ simonmao: 洗 05/10 23:22
90F:→ simonmao: 洗 05/10 23:22
91F:→ simonmao: 洗 05/10 23:22
92F:→ simonmao: 洗 05/10 23:22
93F:→ simonmao: 洗 05/10 23:22
94F:→ simonmao: 洗 05/10 23:22
95F:→ simonmao: 洗 05/10 23:22
96F:→ simonmao: 洗 05/10 23:22
97F:→ simonmao: 洗 05/10 23:22
98F:→ simonmao: 洗 05/10 23:22
99F:→ simonmao: 洗 05/10 23:22
100F:→ simonmao: 洗 05/10 23:22
101F:→ simonmao: 洗 05/10 23:22
102F:→ simonmao: 洗 05/10 23:22
103F:→ simonmao: 洗 05/10 23:22
104F:→ simonmao: 洗 05/10 23:22
105F:→ simonmao: 洗 05/10 23:22
106F:→ simonmao: 洗 05/10 23:22
107F:→ simonmao: 洗 05/10 23:22
108F:→ simonmao: 洗 05/10 23:22
109F:→ simonmao: 洗 05/10 23:22
110F:→ simonmao: 洗 05/10 23:22
111F:→ simonmao: 洗 05/10 23:22
112F:→ simonmao: 洗 05/10 23:22
113F:→ simonmao: 洗 05/10 23:22
114F:→ simonmao: 洗 05/10 23:22
115F:→ simonmao: 洗 05/10 23:22
116F:→ simonmao: 洗 05/10 23:22
117F:→ simonmao: 洗 05/10 23:22
118F:→ simonmao: 洗 05/10 23:22
119F:→ simonmao: 洗 05/10 23:22
120F:→ simonmao: 洗 05/10 23:22
121F:→ simonmao: 洗 05/10 23:22
122F:→ simonmao: 洗 05/10 23:23
123F:→ simonmao: 洗 05/10 23:23
124F:→ simonmao: 洗 05/10 23:23
125F:→ simonmao: 洗 05/10 23:23
126F:→ simonmao: 洗 05/10 23:23
127F:→ simonmao: 洗 05/10 23:23
128F:→ simonmao: 洗 05/10 23:23
129F:→ simonmao: 洗 05/10 23:23
130F:→ simonmao: 洗 05/10 23:23
131F:→ simonmao: 洗 05/10 23:23
132F:→ simonmao: 洗 05/10 23:23
133F:→ simonmao: 洗 05/10 23:23
134F:→ simonmao: 洗 05/10 23:23
135F:→ simonmao: 洗 05/10 23:23
136F:→ simonmao: 洗 05/10 23:23
137F:→ simonmao: 洗 05/10 23:23
138F:→ simonmao: 洗 05/10 23:23
139F:→ simonmao: 洗 05/10 23:23
140F:→ simonmao: 洗 05/10 23:23
141F:→ simonmao: 洗 05/10 23:23
142F:→ simonmao: 洗 05/10 23:23
143F:→ simonmao: 洗 05/10 23:23
144F:→ simonmao: 洗 05/10 23:23
145F:→ simonmao: 洗 05/10 23:23
146F:→ simonmao: 洗 05/10 23:23
147F:→ simonmao: 洗 05/10 23:23
148F:→ simonmao: 洗 05/10 23:23
149F:→ simonmao: 洗 05/10 23:23
150F:→ simonmao: 洗 05/10 23:23
151F:→ simonmao: 洗 05/10 23:23
152F:→ simonmao: 洗 05/10 23:23
153F:→ simonmao: 洗 05/10 23:23
154F:→ simonmao: 洗 05/10 23:23
155F:→ simonmao: 洗 05/10 23:23
156F:→ simonmao: 洗 05/10 23:23
157F:→ simonmao: 洗 05/10 23:23
158F:→ simonmao: 洗 05/10 23:23
159F:→ simonmao: 洗 05/10 23:23
160F:→ simonmao: 洗 05/10 23:23
161F:→ simonmao: 洗 05/10 23:23
162F:→ simonmao: 洗 05/10 23:23
163F:→ simonmao: 洗 05/10 23:23
164F:→ simonmao: 洗 05/10 23:23
165F:→ simonmao: 洗 05/10 23:23
166F:→ simonmao: 洗 05/10 23:23
167F:→ simonmao: 洗 05/10 23:23
168F:→ simonmao: 洗 05/10 23:23
169F:→ simonmao: 洗 05/10 23:23
170F:→ simonmao: 洗 05/10 23:23
171F:→ simonmao: 洗 05/10 23:23
172F:→ simonmao: 洗 05/10 23:23
173F:→ simonmao: 洗 05/10 23:23
174F:→ simonmao: 洗 05/10 23:23
175F:→ simonmao: 洗 05/10 23:23
176F:→ simonmao: 洗 05/10 23:23
177F:→ simonmao: 洗 05/10 23:23
178F:→ simonmao: 洗 05/10 23:23
179F:→ simonmao: 洗 05/10 23:23
180F:→ simonmao: 洗 05/10 23:23
181F:→ simonmao: 洗 05/10 23:23
182F:→ w4a2y4: 洗ㄆ洗 05/11 10:20
183F:→ tra1200: 87 05/11 13:51