108年 - 108 教育部公費留學考試：離散數學#125747

1.(1) We know that

(a) P(1,1) = 2

(b) P(m+1,n)=P(m,n)+2(m+n)

(c) P(m,n+1)=P(m,n)+2(m+n-1)

Prove or disprove the following formula for any positive integers m and n: P(m,n) = (m+n)(m+n-1) - 2n +2

(2) Let f(x) be the ceiling function and let g(x) be the floor function. Let x and y be positive real numbers. Find all conditions of x and y so that f(x+y) = f(x) + g(y) is true.

2.(1)  What is the value of ( mod 17) where mod is the modular operator?

(2)  Prove or disprove the following statement: the sum of the squares of two

(1)  Give all conditions of x and y so that K(x,y) has a Hamilton cycle.

(2)  What is the independence number of K(x,y)?

4.(1)  Transform this logic formula consisted of three Boolean variables X, Y, and Z in the sum-of-products form into its equivalent product-of-sums form.

X dot not(Y) dot Z + not(X) dot Y dot Z + not(X) dot not(Y) dot not(Z)

(2)  A Boolean variable can have either the value "T" which stands for true or "F" which stands for false. List all values of the Boolean variables X, Y and Z so that (X + Y + not(Z)) = X dot Y dot Z

(1)  What is the mean value of X?

(2)  We now change the experiment setup. When a ball is picked, it is removed from the box for the rest of the experiment. Let N be no greater than R+B. What is the mean value of X now?