課程名稱︰離散數學 課程性質︰資工系大一選修 課程教師︰呂育道 開課學院： 開課系所︰ 考試日期（年月日）︰ 考試時限（分鐘）：180 mins 試題 : 1. Consider a binary string x_1x_2...x_n. The (Hamming) weight of x_1x_2...x_n is defined as \sum_i x_i. Two strings have Hamming distance d if they differ i n d positions. Among the strings, how many have an even weight? Ans: \sum_{i = 0}^{\floor(n/2)} C(n, 2 * i) This is because 1 occurs in 2i positions. Then apply a corollary of binomial theorem to add up to 2^{n - 1} 2. How many non-negative integer solutions can satisfy the inequality x_1 + x_2 + x_3 + x_4 + x_5 <= 20, where x_1 >= 1, x_2 >= 2, x_3 >= 3, x_4 >= 4, x_5 >= 5 ? Ans: 252 3. Let f : A → B be invertible. Then there is a unique function g : B → A such that g \circ f = 1_A and f \circ g = 1 \circ B. Prove that f is invertible if and only if it is bijective. Ans: See p. 329 of the lecture notes. 4. Suppose that candidate A receives m votes and candidate B receives n votes with m > n. Assume each vote counting sequence is equally likely. Prove that the probability that A will be strictly ahead of B throughout the vote count is (m - n) / (m + n). (Hint: The reflection principle says for k, a, b > 0, the number of paths on the lattice from (0, k) to (a, b) which touch the origin is equal to the number of paths from (0, -k) to (a, b).) Ans: Consider the number of ways candidate A is always in the lead. A must get the first vote. So A has m 1 additional votes to be counted and B has n. Thin k of a vote for A as +1 and a vote for B as -1. We need to count the number of vote counting sequences and subtract from it the number of vote counting sequ ences where A’s vote count is even with B’s at least once. The former is cle arly C(m + n - 1, m - 1). The latter equals the number of lattice paths from ( 1, 1) to (m + n, m - n) which touch the x-axis. By the reflection principle, i t equals the number of lattice paths from (1,-1) to (m + n,m - n). This is equ ivalent to A getting m votes and B getting n - 1 votes. So the desired count i s C(m + n - 1, m - 1) - C(m + n - 1, m) = (m - n)/(m + n) * C(m + n, n). As th e total number of voting sequences is C(m + n, n), the probability that candid ate A is always in the lead is (m - n) / (m + n). 5. Use induction to prove that F_{n+1}F_{n-1} - (F_n)^2 = (-1)^n where F_n is a Fibonacci number and n∈Z+ with F_0 = 0 and F_1 = 1. Ans: 略 6. Let A = {1, 2, 3} and B = {1, 2, 3, 4, 5}. Determine the number of relation s from A to B and the number of functions from A to B. Ans: There are 2^15 relations from A to B and 5^3 of these are functions from A to B. 7. Let (A, R) be a poset and x ∈ A be the greatest element. Argue that x must be the only maximal element of A. Ans: By contradiction, assume that x′ is another maximal element of A. T x) ∈/ R and (x, x′) ∈/ R violet antisymmetricity. 8. R is antisymmetric if (x, y) ∈ R Λ (y, x) ∈ R \rightarrow x = y for all x,y ∈ A. Let A have n members. How many relations are there that are both antisymmetric and symmetric? Ans: 1 9. Let A = {1, 2, 3, 4, 5}. Determine the number of bijective functions f : A → A which satisfy f(1) ≠ 1, f(2) ≠ 2 and f(3) ≠ 3. Ans: 5! - C(3, 1) ? 4! + C(3, 2) ? 3! - C(3, 3) ? 2! = 64 10. Let S = {1,2,3,...,200} and T be a subset of S with size 101. Prove that there are two integers in T such that one is a multiple of the other. Ans: For each x \in S, we may write x = 2^k*y with some integer k and odd integer y. There are at most 100 such y in T. Since 101 integers are selected from S, by the pigeonhole principle there are two distinct integers a = 2my and b = 2ny for some y ∈ T. If m < n, then a|b; otherwise, b|a. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.37.182.241 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1655308812.A.33D.html ※ 編輯: sN0w374625cS (114.37.182.241 臺灣), 06/16/2022 00:19:06 ※ 編輯: sN0w374625cS (114.37.182.241 臺灣), 06/16/2022 00:54:45