课程名称︰离散数学 课程性质︰电机系二选一必修 课程教师︰郭斯彦 开课学院：电资学院 开课系所︰电机系 考试日期（年月日）︰110.06.21 考试时限（分钟）：110 试题 : 1. (10 points, 1 point each) Answer T(True) or F(False) for each of the follow- ing: (a) There exist integers x and y such that 21x + 54y = 3/ (b) Let m be a positive integer, and a_1,...,a_n be integers. If m divides a_1a_2...a_m, then m divides a_i for some i. (c) Rolling a total of 8 when three dice are rolled is less likely than when t- wo dice are rolled. (d) The next largest permutation of 234651 is 235146. (e) If a is an integer and m is a positive integer, then a^{m-1} ≡ 1(mod m). (f) Recursive algorithm is always more efficient than its iterative counterpart (g) 1 + 10 + 100 + .. + 10^{1000} = 10^{1001} - 1. (h) Let I_n denote the number of injective functions from {1,2,...,n} to {1,2,...,55}. If m \geq n then it must be the case that I_m \geq I_n. (i) In a group of five people, where each two are either friends or enemies, t- ere must be either three mutual friends, or three mutual enemies. (j) If the set of prime numbers that divide x is the same as the set of prime numbers that divide y, then x = y. 2. Short answers (14 points, 2 points each) (a) Suppose k \geq 1 and (x_1,...,x_k) is a randomly chosen k-permutation of {1,...,n} (i.e., an ordered arrangement of k distinct elements, chosen uni- formly from all such arrangements). What is the probability that it is a s- trictly increasing sequence, i.e., x_1 < x_2 < ... < x_k. (b) A palindrome is a string whose reversal is identical to the string. How ma- ny bit strings of length n are palindromes? (c) The parliament of an unnamed country has 57 members from the Workers Party and 72 from the Fat Cats Party. How many ways are there to select an 11 member committee, including a chairperson, if the chairperson must be a member of the majority party, and the other 10 members must be evenly split between the two parties? Express the answer as a formula for the number. Y- ou do not need to evaluate the formula. (d) How many strings of length 9 over the alphabet {a, b, c, d} have either ex- actly three b's or exactly five c's? (e) What is the number of ways to place n distinguishable balls into k disting- uishable bins where no two balls are placed in the same bin? You may assume that n \leq k. (f) What is the number of ways to divide d dollar bills among p people? Assume dollar bills are indistinguishable and people are distinguishable. (g) How many solutions does x_1 + ... + x_k = n have if each x_i (1 \leq i \leq k) must be a positive integer (at least 1)? 3. (4 points, 2 points each) A binary relation R on set A is an equivalence re- lation if R is reflexive, symmetric and transitive. A binary relation R on set A is circular iff for all a, b, c \in A (if aRb and bRc then cRa). Prove the f- ollowing statements. (a) If R is reflexive and circular then R is an equivalence relation. (b) If R is an equivalence relation then R is circular. 4. (15 points, 3 points each) Calculate the following: (a) How many distinct functions f : {1, 2, 3, 4, 5} -> {1, 2, 3} are there, fr- om the set {1, 2, 3, 4, 5} to the set {1, 2, 3}, whose range is a set of s- ize exactly 2? (b) How many surjective functions from a set with 10 elements to a set with 6 elements are there? (Hint: count how many non-surjective functions there are.) (c) Let n be an integer. How many different integers are there in the following set: {n, \floor*{\frac{2n+1}{2}}, n+1/2, \ceil*{\frac{2n-1}{2}} ? (d) Calculate the remainder (-56)^{2016} mod 13. (e) Find x mod100 for the following: 17x + 57 ≡ 22 (mod 100). 5. (6 points, 3 points each) Recursive definition and function (a) Give a recursive definition of the set of positive integers not divisible by 5. (b) Give the function that reverses a string (Hint: a string of length greater than 0 can be represented as xy where x is the first symbol of the string and y is the rest of the string. For example, for string abcd, we have x = a and y = bcd.) 6. (6 points, 3 points each) https://imgur.com/AObKaly (a) Let n = 22, and e = 3. What is the decryption key, "d" ? Briefly explain/ justify your answer. (b) Explain why one can find the decryption key in part (a), but in general ha- ving only“n”and“e”won't let you easily find the decryption key for“re- al-world" instances of RSA. 7. (4 points) Use induction to prove the following (you must use induction, any other proof technique will get zero points). f_1 + ... + f_n = f_{n-2} - 1 for all n \geq 1, where f_n is the n-th Fibon- acci number. 8. (6 points, 3 points each) Given the information 10^{44460} ≡ 32287 mod 44461 10^{50850} ≡ 1 mod 50851 (a) What can you conclude about whether 44461 is a prime or composite number , and why? (you must give reasons to get full credit). (b) What can you conclude about whether 50851 is a prime or composite number , and why? (you must give reasons to get full credit). 9. (4 points) Find the number of permutations of the 26 English letters that do not contain not contain any of the strings RUN, WALK, or SWIM in consecutive positions. (Hint: inclusion-exclusion principle) 10. (9 points) The following questions are independent of each other. (a) Find the general solution to the recurrence a_n = 8a_{n-1} - 16a_{n-2} (3 points) (b) Find the general solution to the recurrence a_n = 8a_{n-1} + 9a_{n-2} (3 points) (c) Find a particular solution to the recurrence a_n = 8a_{n-1} + 9a_{n-2} + 16n (3 points) 11. (6 points, 2 points each) (a) Find a recurrence relation for the number of ways to climb n stairs if the the person climbing the stairs can take one stair or two stairs at a time. Explain your answer. (b) What are the initial conditions? (c) How many ways can this person climb 11 stairs? 12. (4 points) Use Bezout's theorem to prove that if a is relatively prime both to b and to c, then a is relatively prime to bc. That is: gcd(a, b) = gcd(a, c) = 1 -> gcd(a, bc) = 1. 13. (8 points, 4 points each) (a) Suppose p is a prime number other than 2 (so p is odd). Show that for every integer a not divisible by p, if the congruence x^2 ≡ a (mod p) has a solution, then a^{(p-1)/2} ≡ 1 (mod p). (b) Suppose that the prime number p in part (a) has the form p = 4k + 3, w- here k is an integer. Show that if a^{(p-1)/2} ≡ 1 (mod p), then x ≡ a^{k+1} (mod p) is a solution of the congruence in part (a). 14. (4 points) Pigeonhole principle There are 51 houses on a street. Each house has an address between 1000 and 1099, inclusive. Show that at least two houses have addresses that are consecu- tive integers. --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.24.173.199 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1624761518.A.A2D.html