COMP151101

Introduction to Discrete Mathematics

Semester 2 2018/2019

Question 1

In a standard deck of cards there are 4 suits:  clubs, diamonds,  hearts  and spades.   Each  suit contains 13 cards:  2, 3, . . . , 10, J, Q,K, A.  So there are 4 · 13 = 52 cards, in the deck.  A poker hand is a 5-card subset of the standard deck of cards.

(a)  How many diferent poker hands are possible?   [3 marks]

(b)  How many poker hands contain two clubs, two diamonds and one spade?    [3 marks]

(c)  How  many poker hands contain at least one spade?     [3 marks]

[Question 1 Total: 9 marks]

Question 2

Consider distributing 30 identical balls into 10 distinct boxes numbered 1; . . . ; 10.

(a)  In  how many ways can this be done?    [3 marks]

(b)  What is the number of such distributions in which odd numbered boxes are nonempty?    [3 marks]

(c)  What is the number of such distributions in which the number of balls that each box receives is a multiple of 3?  (So we are interested in distributions in which for every i ∈ {1; . . . ; 10}, there exists a nonnegative integer ki  such that the number of balls that box i receives is 3ki.)    [3 marks]

[Question 2 Total: 9 marks]

Question 3

(a)  What is the coefficient of x2y3  when the expression (3x - 2y)5  is expanded?     [3 marks]

(b)  What is the coefficient of x5y3  when the expression (x + y + 2)10  is expanded?    [3 marks]

[Question 3 Total: 6 marks]

Question 4

Three coins are tossed:  a 5p coin, a  10p coin and a 20p coin.  Let  A be the event that an odd number of tails appear.  Let B  be the event that at least two heads appear.

(a) What is the probability of A?    [3 marks]

(b) What is the probability of B?    [3 marks]

(c) What is the probability of A ∩ B?    [3 marks]

(d)  Are the events A and B independent?  (You must justify your answer!)    [3 marks]

[Question 4 Total: 12 marks]

Question 5

(a)  Define the following:

•  a path of length n (where n is a nonnegative integer);

• a cycle;

•  a simple cycle.       [6 marks]

(b)  Prove that every odd closed path C contains an odd simple cycle. (Hint:  use induction on the length l of C.)     [6 marks]

[Question 5 Total: 12 marks] 

[Grand Total: 48 marks]