課程名稱︰離散數學
課程性質︰電機系必修
課程教師︰郭斯彥
開課學院：電機資訊學院
開課系所︰電機系
考試日期（年月日）︰2016/6/20
考試時限（分鐘）：14:20~16:20
試題 :
註：由於試題卷與答案卷一併繳回，因此我只將記得的打上去，可能和原題不太一樣
敬請見諒，謝謝！
1. Answer True of False for each of the following
(a) C(n,n)=1
(b) There are 11! distinct orderings of the letters of the word MATHEMATICS
(c) Rolling a total of 8 when three dice are rolled is more likely than
rolling a total of 8 when two dice are rolled
(d) The next larger permutation of 234651 is 235146
p-1
(e) Let p be a prime, then x ≡1(mod p) for all x∈N.
(f) Recursive algorithm is always more efficient than its iterative
counterpart
1000 1001
(g) 1 + 10 +100 + ... + 10 = 10 - 1
2 5
(h) Σ Σ 1 = 1
i=1 j=1
(i) If the graph of relation contains no arrows at all, then the relation is
symmetric
(j) Zero is a multiple of 7
T F F T F F F F T T
2. How many strings of decimal digits (0,1,2,...,9) of length 10 have
a)Exactly three 0?
b)At least three 0?
c)Sum of all 10 digits equals to 3?
3. A relation R on a set A={1,2,...,10} is defined by a+b=10 where a belongs to
set A and b belongs to set A and(a,b) belongs to set R . Plain answer
without reasons will not get any points for part(b),(c),(d), and (e)
(a) Find the relation R.
(b) Is R symmetric?
(c) Is R antisymmetric?
(d) Is R irreflexive(not reflexive)?
(e) Is R transitive?
4. Calculate the following
(a) What is the probability that a five-card poker hand contains three
queens, one jack, and one 5.
(b) When rolling three dice, what is the probability of getting the sum 6.
(c) Use the Euclidean algorithms to find gcd(952,340).
5. (a)Give a recursive definition of the set of positive integers not divisible
of 5.
(b)Give the function that reverses a string (Hint:a string of length greater
than 0 can be represented as xy where x is the first symbol of the string
and y is the rest of the string. For example, for string abcd, we have
x=a and y=bcd.)
6. Let a,b,c be integers. Use the pigeonhole principle to prove that
(a-b)(b-c)(c-a) is always even.
Every number is either odd of even. By pigeonhole principal,
at least two of the numbers a,b,c are both odd or even. In each case
the difference between them is always even. Thus (a-b)(b-c)(c-a) is
always even.
7. Equivalence Relations: Are the following relations on the set of all people
equivalence relations? If not, give a reason.
(a) R={(a,b)| a and b are the same age}
(b) R={(a,b)| a and b have the same parents}
(c) R={(a,b)| a and b share a common parent}
(d) R={(a,b)| a and b have met}
(e) R={(a,b)| a and b speak a common language}
(a) Yes (b) Yes (c) No (d) No (e) No
8. Calculate the following
145 36 19
(a) 19 (mod 13) (b) (-12) *50 (mod 7)
2 n
9. Use induction on n to prove the following: For any integer n > 4, n < 2 .
10. Modulo arithmetic: solve the following equation for x and y modulo the
indicated modulus, or show that no solution exists. Show your work.
(a) 7x≡1 (mod 15)
(b) 10x+20≡11 (mod 23)
(c) the system of simultaneous equations 3x+2y≡0 (mod 7)
and 2x+y≡4 (mod 7) Ans: x≡1(mod 7), y≡2(mod 7)