99年私立元智大學資工所離散數學

1.

Suppose P(x, y) is a predicate and the universe for the variables x and y is {1, 2, 3}. Suppose P(1, 3), P(2, 1), P(2, 2), P(2, 3), P(3, 1), P(3, 2) are true, and P(x, y) is false otherwise. Which of the following statements are true?

(A)

¬∃x ∃y (P(x, y) ∧ ¬P(y, x)).

(B)

∀y ∃x (P(x, y) → P(y, x)).

(C)

∀x ∃y P(x, y).

(D)

∀y ∃x (x ≤ y ∧ P(x, y)).

2.

Which of the following statement are true?

(A)

Let a and b be integers. If a ≡ b (mod 3), then a² ≡ b² (mod 3).

(B)

Let a and b be integers. If a² ≡ b² (mod 3), then a ≡ b (mod 3).

(C)

Let n be a positive integer. If a₁ = 10, a₂ = 5, and a_n = 2a_n−1 + 3a_n−2, for n ≥ 3, then 5 divides an.

(D)

The system of congruences x ≡ 2 (mod 6) and x ≡ 3 (mod 9) has no solutions

3.

Which of the following statements are true?

(A)

log(n!) is O(n log n).

(B)

(n log(n + 1))² + (log n + 1)(n² + 1) is O(n² log n).

(C)

1² + 2² + 3² + ... + n² is O(n²).

(D)

4.

Which of the following statements are true?

(A)

There is exactly one greatest element in a poset, if such an element exists.

(B)

There is exactly one maximal element in a poset with a greatest element

(C)

If R and T are equivalence relations on the set S, then R ∩ T is also an equivalence relation

(D)

If R and T are equivalence relations on the set S, then R ∪ T is also an equivalence relation.

5.

______ numbers must be selected from the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} to guarantee that at least one pair of these numbers add up to 11.

6.

The coefficient of x³⁰ in the power series of the function (x³ + x⁶ + x⁹ + ...)⁵ is ______.

7.

Let R = {(x, y) | x − y is an integer} is the equivalence relation on the set of rational numbers. The equivalence class ofis ______.

Let T be a full 3-ary tree of height h.

8.

The minimum number of vertices in T is ______.

Let T be a full 3-ary tree of height h.

9.

The maximum number of vertices in T is ______.

Suppose that the cardinality of set A is 4, i.e., |A| = 4.

10.

The number of binary relation on A is ______

Suppose that the cardinality of set A is 4, i.e., |A| = 4.

11.

The number of symmetric binary relations on A is ______.

Suppose that the cardinality of set A is 4, i.e., |A| = 4.

12.

The number of onto functions defined from A to A is ______.

Suppose that the cardinality of set A is 4, i.e., |A| = 4.

13.

The number of 1−1 functions defined from A to A is ______.

Consider the graphs, complete graph on 6 vertices, K₆, complete bipartite graph with vertex set partitioned into two subsets of 4 vertices, K_4,4, and 3-dimensional hypercube, Q₃.

14.

List the graphs each of which has a Hamilton circuit. ______.

Consider the graphs, complete graph on 6 vertices, K₆, complete bipartite graph with vertex set partitioned into two subsets of 4 vertices, K_4,4, and 3-dimensional hypercube, Q₃.

15.

List the graphs each of which has an Euler circuit. ______.

Consider the graphs, complete graph on 6 vertices, K₆, complete bipartite graph with vertex set partitioned into two subsets of 4 vertices, K_4,4, and 3-dimensional hypercube, Q₃.

16.

List the chromatic number of each of the graphs. ______.

17.

How many non-isomorphic unrooted trees are there with four vertices? Draw examples of each of these.

18.

Suppose that f(n) satisfies the divide-and-conquer relation and f(1) = 2. What is f(4^k) for k ≥ 1?