99年私立逢甲大學資工所離散數學

1.

Sixty students, each with $30 dollars, visited an arcade that has the following three games: Super Mario, age of Empires, and Red Alert. Eighteen of the students played each of the three games, and 25 of them played at least two of them. No student played any other game at the arcade, nor did any student play a given game more than once. Each game costs $10 dollars to play, and the total proceeds from the students visit were $800 dollars. How many of these students preferred to watch and played none of the games?

2.

One hundred students enter a locker room that contains 100 lockers. The first student opens all the lockers. The second student changes the status (from open to closed, and vice versa) of every other locker, starting with the second locker. The third student then changes the status of every third locker, starting with the third locker. In general, for 1 ≤ k ≤ 100, the kth student changes the status of every kth locker, starting with the kth locker. After the 100th student has gone through the lockers, which lockers are left open?

3.

Prove that for all real numbers x, y and z, if x + y + z ≥ 90, then x ≥ 30 or y ≥ 30 or y ≥ 30.

For n in Z⁺, define Xn = {1, 2, 3, …, n}. Given m, n in Z⁺, f : X_m → X_n is called monotone decreasing if for all i, j in X_m, 1 ≤ i < j ≤ m ⇒ f(i) ≥ f(j).

4.

How many monotone decreasing function are there with domain X₁₀ and codomain X₈?

For n in Z⁺, define Xn = {1, 2, 3, …, n}. Given m, n in Z⁺, f : X_m → X_n is called monotone decreasing if for all i, j in X_m, 1 ≤ i < j ≤ m ⇒ f(i) ≥ f(j).

5.

Determine the number of monotone decreasing functions f : X₁₀ → X₈ where f(4) = 6 and f(6) = 3.

A full binary tree is a binary tree in which every node other than the leaves has two children.

6.

(a) Find the number of full binary trees with 5 leaf nodes.
(b) Find the number of full binary trees with n leaf nodes, where n is an arbitrary integer and n ≥ 1.

7.

In how many ways can one arrange five 1's and five −1's so that all ten partial sums (starting with the first summand) are nonnegative?

8.

Give an example of three sets W, X, Y such that W ∈ X and X ∈ Y but W ∉ Y.

9.

If a, b, c ∈ Z and 31|(5a + 7b + 11c), prove that 31|(21a + 17b + 9c).

Let A = {1, 2, 3, 4, 5, 6}.

10.

How many relations on A are equivalence relations?

Let A = {1, 2, 3, 4, 5, 6}.

11.

How many of the equivalence relations in part (a) satisfy 1, 2 ∈ [4]?

12.

Solve the recurrence relation a_n − 3a_n−1 = 5(3ⁿ), where n ≥ 1 and a₀ = 2.