=========================preview======================
(comp170)[2009](s)mid1~PPSpider^sol_10159.pdf
Back to COMP170 Login to download
======================================================
Hong Kong University of Science and Technology
COMP170: Discrete Mathematical Tools for Computer Science
Spring 2009
Midterm Exam 1
10 March 2009, 3:00C4:20pm, LT-E
Solutions
Question 1: Any subset of the 12 points with three or more members can be made into exactly one convex polygon. Thus, this problem is equivalent to counting the number of such subsets.
12
Since the number of k-element subsets is , the total number of subsets is equal to
k
12122
12 1212
= .
k kk
k=3 k=0 k=0
212
212 .
=
k
k=0
= 4096 . 1 . 12 . 66
= 4017.
Question 2: A surjective function from A to B has to be either one of the following two cases:
(i)
It maps three elements in A to the same element in B and the remaining k . 3 elements in A to the remaining k . 3 elements in B.

(ii)
It maps two elements in A to the same element in B, another two elements in A to a di.erent element in B, and the remaining k . 4 elements in A to the remaining k . 4 elements in B.


k
For case (i), the number of ways of choosing the triple is . Once the triple is chosen,
3
there are (k . 2)! ways of mapping the (k . 2) groups in A to B.
1 kk.2
For case (ii), the number of ways of choosing two pairs is . Once the two pairs
22 2
are chosen, there are (k . 2)! ways of mapping the (k . 2) groups in A to B.
By the sum principle, the total number of surjective functions is
.. ... . ...... ..
k 1 kk . 2 k 1 kk . 2
(k . 2)!+ (k . 2)!= + (k . 2)!
3 222 3222
Question 3: (a) Let us consider the problem of putting n students into three classrooms so that the .rst, second and third classrooms contain r, s and t students, respectively. The number of ways of doing this is equal to the following trinomial coe.cient:
n
.
rst
We now use a di.erent way of counting, say by assuming that one speci.c student wears a hat. This hat-wearing student may be put in the .rst, second or third
1 classroom. If the student is put in the .rst classroom, the number of ways of putting the other students is equal to
n . 1
.
(r . 1) st Similarly, if the student is put in the second or third classroom, the number of ways of putting the other students is equal to
n . 1 r (s . 1) t
or ..
n . 1
,
rs (t . 1) respectively. Since these three cases form three mutually disjoint sets that together cover all possibilities, we can apply the sum principle to show that
nn . 1 n . 1 n . 1
=++ .
rst (r . 1) st r (s . 1) t rs (t . 1)
(b) The right-hand side (RHS) of the identity can be expanded as:

n . 1 n . 1 n . 1
RHS= ++
(r . 1) st r (s . 1) t rs (t . 1)
(n . 1)! (n . 1)! (n . 1)!
= ++
(r . 1)! s! t! r!(s . 1)! t! r! s!(t . 1)! r(n . 1)! + s(n . 1)! + t(n . 1)!
=
r! s! t!
n!
=
r! s! t!
n
=
rst
which is equal to the left-hand side (LHS).
Question 4: (a) Since there are 5 distinct letters in LITTLEST and no repetition of letters is allowed, by the product principle, there are 5 4 3 = 60 distinct 3