105年 - 105 國立中山大學_碩士班招生考試_資工系(甲組)：離散數學#105816

試卷資訊

選擇題 (0)

申論題 (7)

1. Show that for any positive integer n, there exists a positive integer m such that n divides m (namely, m = kn for some integer k), and the decimal digits of m are only O and 1. For example, n = 7, m? = 1001. In addition to show that this is true in general, use n = 7 and n = 12 to show how to find such m.

2. Let N be the set of all positive integers, and S = N x N, (namely, S = [(x, y) I x, y ∈ N]). Show that there is a bijection (one-one and onto) function f :S → N, or show that no such function exists.

3. Let m ＞ 1 and n ＞ 1 be two positive integers. Let r(m, n) denotes the moimum number of rectangles defined by m horizontal limes and n vertical lines in a plane. Derive a formula for r(m,n), and justify your answer. Note that rectangles mnay overlap. For example, let m = 2 and n=3( , r(2,3) = 3, not 2.

4. A line segment in R² is a line joining 2 different points in R². Two lines intersect if they share a common point. Show that in any 6 line segments in R², either there are 3 line segments in which any pair of them intersect or there are 3 line segments in which no pair of them intersect.

5. Let the sequence of numbers g₀, g₁, ... ,,be defined by g₀ = 0, g₁ = 1, and, for every n ＞ 1, . Solve in terms of n, by the method of generating functions.

6. The girth of a graph G is the length of the shortest cycle in G. Let G be a simple graph with y vertices, e edges, and girth g. It is known that if G is planar, then e . Let K₅ be a complete graph with 5 vertices, K₅and K₃,₃ be a complete bipartite graph with 3 vertices in each partition. Draw Ks and K₃,₃, and show that they are not planar.

7. Let L be the set of binary strings whose values are multiple of 7, (namely, L = {0, 111,1110,10101, .}). Design a finite state machine M = (Q, Σ,δ,q₀, F) to recognize the language L. Although no formal proof is required, you should explain why your machine M accepts only strings in L, and every binary string in L is accepted by M.