99年國立台北大學資工所離散數學

A black box contains 7 balls numbered 1, 2, 3, …, 7, respectively. The experiment has 5 steps. In each step, a ball is picked out to record its number and then it is put back into the box.

1.

Compute the probability that the 5 recorded numbers are all different

A black box contains 7 balls numbered 1, 2, 3, …, 7, respectively. The experiment has 5 steps. In each step, a ball is picked out to record its number and then it is put back into the box.

2.

Given that the sum of the first 3 recorded numbers is even, compute the conditional probability that the sum of the 5 recorded numbers is odd.

A black box contains 7 balls numbered 1, 2, 3, …, 7, respectively. The experiment has 5 steps. In each step, a ball is picked out to record its number and then it is put back into the box.

3.

Compute the probability that the sum of the 5 recorded numbers is even.

A black box contains 7 balls numbered 1, 2, 3, …, 7, respectively. The experiment has 5 steps. In each step, a ball is picked out to record its number and then it is put back into the box.

4.

Compute the probability that "2" appears even times in the 5 recorded numbers.

Determine whether each following argument is valid or not. If it is valid, prove it; otherwise, give a counterexample to disprove it.

5.

Determine whether each following argument is valid or not. If it is valid, prove it; otherwise, give a counterexample to disprove it.

6.

7.

Solve the recurrence relation a_n = (4/n)(a₁ + a₂ + ... + a_n−1) for the initial condition a₁ = 1.

Boolean function f(w, x, y, z) = (¬w ∧ ¬x ∧ ¬y) ∨ (x ∧ ¬y ∧ ¬z) ∨ (x ∧ y ∧ z) ∨ (¬w ∧ x ∧ z) ∨ (w ∧ x ∧ ¬y) ∨ (w ∧ ¬x ∧ ¬y).

8.

Show the logic table of the Boolean function f.

9.

Express f as a Boolean expression in DNF (Disjunctive Normal Form).

Boolean function f(w, x, y, z) = (¬w ∧ ¬x ∧ ¬y) ∨ (x ∧ ¬y ∧ ¬z) ∨ (x ∧ y ∧ z) ∨ (¬w ∧ x ∧ z) ∨ (w ∧ x ∧ ¬y) ∨ (w ∧ ¬x ∧ ¬y).

10.

Draw a combinatorial circuit with AND, OR, NOT gates to realize f where the number gates is minimized.

Boolean function f(w, x, y, z) = (¬w ∧ ¬x ∧ ¬y) ∨ (x ∧ ¬y ∧ ¬z) ∨ (x ∧ y ∧ z) ∨ (¬w ∧ x ∧ z) ∨ (w ∧ x ∧ ¬y) ∨ (w ∧ ¬x ∧ ¬y).

11.

Transform and redraw the above combinatorial circuit to contain NAND gates only.

12.

Prove the following statement.
For n ≥ 1, let a₁, a₂, …, a_n be a sequence of n integers where they are not necessarily positive and not necessarily all distinct. Then there exists a non-empty subsequence a_i, a_i+1, …, a_j such that the sum a_i + a_i+1 + ... + a_j is a multiple of n.

For n, m ≥ 2, the Ramsey number R(m, n) is the smallest k such that every graph on k vertices has either a clique of size m or an independent set of size n.

13.

Show that R(m, n) ≤ R(m, n − 1) + R(m − 1, n).

For n, m ≥ 2, the Ramsey number R(m, n) is the smallest k such that every graph on k vertices has either a clique of size m or an independent set of size n.

14.

R(2, n) = n.

For n, m ≥ 2, the Ramsey number R(m, n) is the smallest k such that every graph on k vertices has either a clique of size m or an independent set of size n.

15.

What is R(3, 4)?

For n, m ≥ 2, the Ramsey number R(m, n) is the smallest k such that every graph on k vertices has either a clique of size m or an independent set of size n.

16.

Show that R(3, 5) ≤ 14.

17.

Consider the adjacency matrix of some undirected graph given as follows: