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 p2mod 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.)

1.The fornat of IEEE single-precision /loating-point standard representation requires 23 fiaction bits, 8 exponent bits, and I sign bit, with a total of 32 bits for each word. Convert the following binary number in the IEEE single-precision format to its decimal format. (10%)

a) Draw the logic circuit. (5%)

b) Show the truth table for the given logic statement. (5%)

3. The seven stages in a von Neumann fetch-execute cycle are shown in the table below. Put each stage in the correct sequence by writing the numbers 1 to 7 in the right hand column. (10%)

a) Parity check (3%)

112年 - 112 國立臺灣大學_碩士班招生考試:數學(B)#130247

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

109年 - 109 國立臺灣大學_碩士班招生考試_電機工程研究所丙組:離散數學(B)#105860