110年 - 110台灣聯合大學系統_碩士班招生考試_電機類:離散數學#104950

(a) [3 points! If ax ay (mod n), then x y (mod n).

(b) [3 points) If x

y (mod n), then ax

ay (mod n).

(c) [3 points) The set of integers and the set of prime nu umbers have the same cardinality.

(d) [3 points) If a relation is symmetric and transitive, then the relation is rellexive.

(e) [3 points] .

(f) [3 points] 5 dividesn⁵- n whenever n is a positive integer.

(g) I points Given a,bent and gcdta, band gcd(a，b)≠ 1 , we cannot find an inverse of a modulo b in some cases.

(a) [6 points) Compute the expected number of vertices and edges that remain after the deletion process.

(b) I6 pointsI Based on Ca), ty to infer that for any graph with n vertices with nd/2 edges, there is an independent set with at least n/2d vertices.

3. A treed that never gave up on its dream to flourish. [10 points] Let T be a spanning tre

n edge cost function c. T is defined to have the cycle property if for any edge

the cycle generated by adding e' to T. Also, T is defined to have the cut property if for any edge

for all e' in the cut defined by e. Show that the following three statements are equiva

1. T has the cycle property.
2. T has the cut property.
3. T is a minimun cost spanning tree.

4. Respect for the ancients. [8 points Find an integer x such that x 1 (mod 3), x 3 (mod 7) and x 9 (mod11).

5. Show time! (10 points] Prove that for every positive integer n, there are n consecutive composite integers. In other words, prove that we can find n consecutive composite integers for any n.

(a) [6 points] Prove that any Sprouts game consists of a finite number of moves before someone loses. In other words, the game will terminate eventually.

(b) [7 points] Show a tight upper bound on the worst -case number of moves in a Sprouts game that starts with n dots, and prove your answer.

7. Act together, we go far. [12 points) Suppose we have two isomorphic graphs G₁ and H₁, as well as two isomor- phic graphs G₂ and H₂. Prove or disprove tha are also isomorphic.

(a) [7 points] Use the recurrence tree method to solve the time complexity of recurrence T(n) = 3T(n/4]) + θ(n²) in theθ-notation.

(b)[7 points] Solve the time complexity of recurrence in the θ-notation without using Master method.

110年 - 110台灣聯合大學系統_碩士班招生考試_電機類:離散數學#104950

試卷資訊

選擇題 (0)

申論題 (17)