=========================preview======================
(COMP2711)[2013](f)midterm~=od_g^_90441.pdf
Back to COMP2711 Login to download
======================================================
HKUST C Department of Computer Science and Engineering
COMP 2711: Discrete Math Tools for CS C Spring 2013
Midterm Examination

Date: Friday, 11 October 2013 Time: 19:00C21:30
Serial #

Name: Student ID:
Email: Lecture and Tutorial:

Instructions
.
This is a closed book exam. It consists of 13 pages and 8 questions.

.
Please write your name, student ID, email, lecture section and tutorial on this page.

.
For each subsequent page, please write your student ID at the top of the page in the space provided.

.
Please sign the honor code statement on page 2.

.
Answer all the questions within the space provided on the examination paper. You may use the back of the pages for your rough work. The last three pages are scrap paper and may also be used for rough work.

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

.
Solutions can 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.
. Please do not use the nPk and nCk notation. Use nk and nk instead.
Questions 1 2 3 4 5 6 7 8 Total
Score

As part of HKUSTs introduction of an honor code, the HKUST Senate has recommended that all students be asked to sign a brief declaration printed on examination answer books that their answers are their own work, and that they are aware of the regulations relating to academic integrity. Following this, please read and sign the declaration below.
I declare that the answers submitted for this examination are my own work.
I understand that sanctions will be imposed, if I am found to have violated the University regulations governing academic integrity.
Students Name:

Students Signature:
Problem 1: [14 pts] Suppose there are 20 pens, each labeled with a distinct integer from 1 to 20.
(a)
How many ways are there to select 8 pens such that 4 pens have odd labels and 4 pens have even labels?

(b)
Suppose there are two identical bags. How many ways are there to select 8 pens and put them into the two bags such that each bag contains 2 pens with odd labels and 2 pens with even labels?

(c)
How many ways are there to select 8 pens such that the absolute di.erence of the integer labels for each pair of the selected pens is larger than 1?


Explain how your answers are derived.
..2
Solution: (a) 10 4 . There are 10 pens with odd labels. We select 4. Same for the
even ones.
(b) . 10 4 .2. 4 2 .2 /2!. There are . 10 4 .2 ways to select 4 odd pens and 4 even pens. There are . 4 2 .2 ways to select 2 odd pens to group with 2 even
pens and the rest 4 pens form another group. However, this has double
counted the order of the 2 groups, so we divide it by 2! to eliminate . .2. .2

10 8
the double counting. Alternatively