Discrete Math Final Exam PDF

Preview

Summary

Final Exam of Discrete Math in National Tsinghua University...

Description

CS2336 Discrete Mathematics Exam 3 January 06, 2020 (10:10–12:30) Answer all questions. Total marks = 105. Maximum Score = 105/100. Large portion of marks may be deducted for incomplete proofs. 1. (15%) Let A, B, and C be three sets. It is known that the following are true. • • • • • •

|A| = 13; |B| = 11; |A ∩ C| = 6; |A ∪ C| = 24; |B ∪ C| = 20; |(A ∪ C) − B| = 16.

Find |(A ∩ B) − C |. (Hint: Draw a Venn diagram to help.) 2. (a) (10%) Let X and Y be countable sets. Show that X ∪ Y is countable. (b) Let Z = {z | z 2 = n/m for some n, m ∈ N} denote the set of square roots of positive rational numbers. (10%) Using the result of (a), or otherwise, show that Z is countable. 3. Let f : Z+ → Z+ be a function such that f (x) =

(

x + 1 if x is not a multiple of 3 x − 2 if x is a multiple of 3

(a) (10%) Determine if f is one-one. Explain your answer. (b) (10%) Determine if f is onto. Explain your answer. 4. (15%) Let S = {x, y, z}. Construct a binary relation R on S such that R is anti-symmetric and not reflexive, but the transitive closure of R is both symmetric and reflexive. (Note: You may describe R with a directed graph.) 5. (15%) (a) (5%) Draw two non-isomorphic simple connected undirected graphs H1 and H2 , each with 4 vertices and with the same number of edges. (b) (10%) Show that H1 and H2 are non-isomorphic. 6. (15%) (a) (5%) Draw a simple connected undirected graph G with 7 vertices and 10 edges that is non-planar. (b) (10%) Show that G is non-planar. Note: You may assume that Kuratowski’s theorem is correct.

7. (Extremely Challenging; Estimated time to solve is more than 1 hour) There are 4n people and 4n hats, for some positive integer n. Hats are colored with n different types of colors, and for each color there are 4 hats. We distribute a color hat to a person arbitrarily. Now, it turns out that these 4n people are actually 2n pairs of couples. (5%) Show that we can always divide the 2n pairs of couples, evenly, into two groups (each with n pairs), such that within each group, the number of colored hats for each color is 2. Example: Suppose n = 2. There are 8 hats, four of them are white, and four of them are black. Also, there are 4 pairs of couples, A1 − A2 , B1 − B2 , C1 − C2 , D1 − D2 . Scenario 1: If the hats are distributed in the following way: A1 black

A2 B1 white black

B2 black

C1 C2 white black

D1 D2 white white

Then, we can put A1 − A2 and C1 − C2 in a group, and B1 − B2 and D1 − D2 in the other group, so that for each group, the number of colored hats for each color is 2. Scenario 2: If the hats are distributed in the following way: A1 black

A2 black

B1 B2 C1 white white black

C2 black

D1 D2 white white

Then, we can put A1 − A2 and B1 − B2 in a group, and C1 − C2 and D1 − D2 in the other group, so that for each group, the number of colored hats for each color is 2....