=========================preview======================
(comp170)[2009](s)mid1~PPSpider^_10158.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

Instructions
1.
This is a closed-book exam consisting of 6 questions.

2.
Please write your name, student number and email address on the cover page of the answer booklet.

3.
Please sign the honor code statement on the second page of the answer booklet.

4.
All answers must be put on the answer booklet. Only the answer booklet needs to be handed in at the end of the exam.

5.
In the answer booklet each question starts on a new page. This is for clarity and is not meant to imply that your answer needs to .ll up all the space provided.

6.
Unless otherwise speci.ed, you must always explain how you derived your answer. A number without an explanation will be considered an incorrect answer.

7.
Your answers may be written in terms of binomial coe.cients and falling factorials.

For example, 53 + 42 may be written instead of 16, and 53 instead of 60. Calculators may be used for the exam (but are not necessary).

8.
Please do not use the nPk and nCk notation. Use nk and nk instead.

9.
Please put your student ID card on the desk so the TA can check it.

10.
All mobile phones must be turned o. completely during the exam or else you will be disquali.ed.


Question 1: [12 points]
Twelve points are marked on a circle. How many distinct convex polygons of three or more sides can be drawn using some or all of the 12 points as vertices? (The .gure below shows one such polygon formed by four of the 12 points.)

Question 2: [14 points]
Let A = {a1,a2,...,ak} and B = {b1,b2,...,bk.2} be two nonempty sets where k> 3 is a positive integer.
We de.ne surjective functions from A to B. How many such functions can be de.ned?
Question 3: [16 points] Consider the following identity:
nn . 1 n . 1 n . 1
=++ ,
rst (r . 1) st r (s . 1) t rs (t . 1)
where n, r, s, t are positive integers such that r + s + t = n.
(a)
Prove the identity above by means of a combinatorial proof.

(b)
Prove the identity above by means of an algebraic proof.


Question 4: [20 points]
We want to form 3-letter words using the letters in LITTLEST. For the purpose of this problem, a word is considered any ordered list of letters.
(a)
How many distinct 3-letter words can be formed with no repetition of letters allowed? (E.g., LET is legal but SEE is not.)

(b)
How many distinct 3-letter words can be formed with unlimited repetition of letters allowed? (E.g., both LET and SEE are legal.)

(c)
How many distinct 3-letter words can be formed if repeats are allowed but no letter can be used more often than it appears in LITTLEST? (E.g., TTL is legal but LEE is not.)


Question 5: [18 points] We de.ne a sequence of nonnegative integers called Fibonacci sequence as follows:
.
. 0 if n =0 Fn =1 if n =1
.
Fn.1 + Fn.2