MAS1003 Discrete Mathematics: Problem sheet 1

Please hand in solutions to your examples class tutors no later than Monday 25th October

0. [1] Find and bookmark the course web page.

1. [1] Let A = {1, 2, 3, 5, 8}, B = {1, 5, 9} and C = {1, 3, 7, 10}. Find A ∪ B, A ∩ B, (A ∪ B) ∩ C, A ∪ (B ∩ C), A \ C, (A \ C) \ B, A \ (C \ B).

2. [2] Write down the elements of the following sets:

A = {n | n is an integer with −5 ≤ n ≤ 5};
B = {m | m = n(n + 1)/2 where n ∈ A};
C = {a | a = n^{3} where n ∈ A};
D = {n | n ∈ A and n is odd}.

3. [2] Let A, B and C be sets. Verify the following identities using Venn diagrams.

(i) (A ∪ B) \ (A ∩ B) = (A \ B) ∪ (B \ A); (ii) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C); (iii) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C); (iv) A \ (B ∪ C) = (A \ B) ∩ (A \ C);

(v) A \ (B ∩ C) = (A \ B) ∪ (A \ C).

4. [4] Can you draw a suitable Venn diagram depicting four arbitrary sets?

5. [2] 100 students were surveyed about their television viewing. Each of them admitted watching at least one of the following three programmes: Teletubbies, Neighbours and South Park. 44 watch Teletubbies, 50 watch Neighbours, 55 watch South Park, 17 watch Teletubbies and Neighbours, 18 watch Teletubbies and South Park, 21 watch Neighbours and South Park. How many watch all three programmes?

6. [3] Let A, B and C be finite sets. Derive

(i) a formula for |A ∩ B| in terms of |A|, |B| and |A ∪ B|, (ii) a formula for |A ∩ B ∩ C| in terms of |A|, |B|, |C|, |A ∪ B|, |A ∪ C|, |B ∪ C| and |A ∪ B ∪ C|.

7. [3] (Biggs) What is wrong with the following argument? Since one-half of the numbers n in the range 1 ≤ n ≤ 60 are multiples of 2, 30 of them cannot be primes. Since one-third of the numbers are multiples of 3, 20 of them cannot be primes. Hence at most 10 of them are primes.

8. [3] (Biggs) Find the number of ways of arranging the letters A, E, M, O, U, Y in a sequence in such a way that that the words ME and YOU do not occur.

9. [2] A bridge hand consists of 13 cards. How many bridge hands comprise three spade cards, four diamonds, four hearts and two clubs?

10. [3] A poker hand consists of 5 cards. They are ranked according to which combinations of values and suits they contain. One very high ranking hand is four of a kind containing four cards of one value (e.g., four Queens) and one other card. We shall work out how many such hands there are. There are 13 possibilities for the value involved in the four, and after that one can choose the other card in 48 ways, so there are 13 × 48 = 624 four of a kind hands. How many poker hands are there of each of the following types?

(i) full house: three cards of one value, and two of another, for instance, 3♠ 3♡ 3♣ J♠ J♢; (ii) three of a kind: three cards of one value, the other two being of two other values, for instance, 5♠ 5♡ 5♢ A♠ 7♣; (iii) two pairs: two cards of the same value, another two cards of a second value, and the last card being of a third value, for instance, Q♡ Q♣ 8♠ 8♣ 9♢; (iv) pair: two cards of the same value, the other three cards being of three different values, for instance, 4♠ 4♡ A♣ Q♠ J♡. (N.B. There are exactly \binom{52}{5} = 2598960 poker hands altogether, so the sum of your answers should not exceed this!)

11. [1] Calculate Pascal’s triangle up to (at least) the entries in the row with n = 12.

12. [2] Show that

\binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n − k}{r − k}.

13. [3] Let’s define some sums by picking out every third element of the rows of Pascal’s triangle. Let

A_{n} = \binom{n}{0} + \binom{n}{3} + \binom{n}{6} + ⋯, B_{n} = \binom{n}{1} + \binom{n}{4} + \binom{n}{7} + ⋯

and

C_{n} = \binom{n}{2} + \binom{n}{5} + \binom{n}{8} + · · · .

In each case the sum ends when there are no further binomial coefficients to add. E.g., A_{5} = \binom{5}{0} + \binom{5}{3} = 1 + 10 = 11, B_{5} = \binom{5}{1} + \binom{5}{4} = 5 + 5 = 10 and

C_{5} = \binom{5}{2} + \binom{5}{5} = 10 + 1 = 11. Calculate A_{n}, B_{n} and C_{n} for all n up to n = 12. Can you describe the pattern?

RJC 1/10/1999