=========================preview======================
(comp170)[2009](s)final~PPSpider^sol_10157.pdf
Back to COMP170 Login to download
======================================================
Hong Kong University of Science and Technology
COMP170: Discrete Mathematical Tools for Computer Science
Spring 2009
Final Exam
21 May 2009, 12:30C3:00pm, Rm 3007
Solutions
Question 1: (a) True. We prove the identity algebraically. Since
k n! n =(n . k)!
nn!
= ,
kk!(n . k)!
kn
we obtain the identity n= k!.
k
(b) False.
The fact that f : A B is injective means that

.x, y Ax .= y . f(x) .= f(y) .
So B should have at least as many elements as A, i.e., |B||A|.
(c)
False. The two numbers p and q in the RSA algorithm must be prime, but 3534 is not a prime number.

(d)
False. The quanti.ed statement is true as long as there exists a non-CS student x who makes CS(x) false, even though there does not exist any Computer Science student who gets an A+ grade. The correct statement should be:


.x U CS(x) APlus(x) .
(e) True.
By de.nition,

P (A B)
P (A|B)=
P (B) P (B A)
P (B|A)= .
P (A)
So,
P (B|A)P (A)P (A|B)=
P (B)
P (B|A)P (A)

=
P (B (A A))
P (B|A)P (A)

=
P ((B A) (B A))
P (B|A)P (A)

= (because B A and B A are disjoint)
P (B A)+ P (B A)
P (B|A)P (A)

= .
P (B|A)P (A)+ P (B|A)P (A)
Question 2: (a) The problem can be re-stated as follows: Let m = 20 and n = 9 be two positive integers such that gcd(m, n)= gcd(20, 9) = 1 and we have the following two modular equations:
x mod20=13 (1) x mod 9 = 0. (2)
Find the value of x in the range 100 x 200. From the Chinese Remainder Theorem, we know that there exists a unique solution for x in Zmn = Z180. Let us .rst .nd this solution and then check if it satis.es the condition 100 x 200. Let m = 20,n =9,a = 13,b = 0, m is the multiplicative inverse of m in Zn = Z9, and n is the multiplicative inverse of n in Zm = Z20. From the constructive proof for the Chinese Remainder Theorem, the unique solution for x in Zmn = Z180 can be computed as
x = y mod mn = y mod 180
where y = ann + bmm = 13 9 n = 117 n.
Since 9 9 mod 20 = 1,
we have n = 9. Thus y = 117 9 = 1053
and x = 1053 mod 180 = 153.
Because 100 153 200, so x = 153 is the solution.
(b) We note that x = 153 + kmn = 153 + 180k
for any integer k must satisfy both (1) and (2). Since the only value of k that can make x satisfy the condition 500 x 600 is when k = 2, so the value of x is
x = 153 + 360 = 513.
Question 3:

(a) We .rst use an n-tuple (G1,...,Gi,...,Gn) to denote a pairing, where each element Gi .{1,..., 2n}, with |Gi| = 2, contains two numbers that correspond to two of the 2n participants who play together in a game. The number of n-tuples that correspond to di.erent pairings is
2n 2n . 22n . 4 2(2n)!
= .
222 22n
However, note that the order of the elements in an n-tuple is important but it is not important when considering a pairing for the games. Because each pairing is counted n! times using an (ordered) n-tuple representation, the total number of ways to