110年 - 110 國立臺灣大學_碩士班招生考試_部分系所:離散數學(B)#101167

選擇題 (0)

申論題 (6)

1. (13 points) There are 10 different items. The weight of these items are integers between l and 100. A person wants to pick two disjoint non-empty sets of items such that the total weight of one set is the same as the total weight of the other. (Each set may contain any number of items.) Is it always possible to choose these two sets? Prove your answer.

2. (13 points) Solve the following recurrence (show your derivation):

3. (13 points) Let p be a prime. Find all possible values of p²mod 40. Prove the correctness of your answer. (Answering without proof will not receive any credit.)

4. (35 points) For cach of the following statements, determine whether it is true or false. No explanation is needed. You get +5 points for every correct answer and -6 points for every incorrect one, (O points if you do not answer.)
(a)
(b) In propositional logic, (^, -J is a functionally complete set.
(c) There exists a bijective function from
(d) The union of infinitely many disjoint infinite sets must be uncountable.
(e) For any two distinct primes p, g, there exists two integers s,t such that ps + gt = 1.
(f) If relation Rt is antisymmetric, then must be antisymmctric for any relation R.

(g) The set is an equivalence relation on the set of all positive functions

5. (13 points) Let T' be a tree with n leaves and m non-leaf nodes. Suppose that all non-leaf nodes have degree 5. Is n = 3m + 2 always true? You must either prove the equality formally or find a counterexample.

6. (13 points) A football has pentagons and hexagons on its surface (not necessarily regular). Suppose that the seams of these pentagons and hexagons form a cubic graph (a graph with every vertex having degree 3). How many pentagons does this foorball have? Prove your answer formally. (You must prove that no other values are possible.)

110年 - 110 國立臺灣大學_碩士班招生考試_部分系所:離散數學(B)#101167

試卷資訊

選擇題 (0)

申論題 (6)