课程名称︰离散数学
课程性质︰电机系必修
课程教师︰郭斯彦
开课学院：电机资讯学院
开课系所︰电机系
考试日期（年月日）︰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)