MAT2612/102/3/2017

Tutorial letter 102/3/2017

INTRODUCTION TO DISCRETE
MATHEMATICS
MAT2612

Semesters 1 & 2

Department of Mathematical Sciences

ERRATA, THE EXAM AND SOLUTION OF OCTOBER 2016

EXAM PAPER

BARCODE

university
Define tomorrow. of south africa
Dear Student

This tutorial letter contains the following information:

1. ERRATA IN THE PRESCRIBED BOOK

2. THE EXAM
3. THE OCTOBER/NOVEMBER 2016 EXAM PAPER AND SOLUTIONS

1. ERRATA IN THE 6TH EDITION OF KBR

(The following are correct in the 5th edition.)

• p.491: Answers to Exercise 4.4

Some answers have been left out and the numbering is incorrect. Please change the
numbers of the questions as follows:
17 → 19 (i.e. change 17 to 19)
19 → 21
21 → 23
23 → 25
25 → 27
27 → 29
29 → 31
31 → 33
33 → 35
35 → 37
37 → 39

Include the following answers:

13. reflexive
15. reflexive, antisymmetric, transitive
17. irreflexive, symmetric

2. THE EXAM
The exam is two hours long and the paper counts out of 100 marks. Most questions will be
similar to those asked in the self–evaluation tasks and assignments.
You must know and be able to apply all definitions and statements of theorems. However,
you need only know the proofs of the following theorems (YOU MAY BE ASKED TO PROVE
ONE OF THE THEOREMS IN THE EXAM):
Section 3.1: Theorems 3 and 4
Section 3.2: Theorem 1
Section 4.1: Theorem 1
Section 4.7: Theorem 8

2
 MAT2612/102/3/2017

Section 5.1: Theorem 4

Section 6.2: Theorems 1 and 2
Note that the proof of a theorem may be given before the statement of the theorem in KBR.

You may also be asked to give a short proof of a statement by applying definitions and state-
ments of theorems.

You need not know the “Rules for Determining the Θ – Class of a Function” given on p. 203
(6th edition of KBR), p. 186 (5th edition of KBR).

3. THE OCTOBER/NOVEMBER 2016 EXAM PAPER AND SOLUTIONS

This is the October/November 2016 exam paper. The best way to use this in your preparation for
the exam, is the following:
• First, revise your work;
• try to do this exam without looking at the solutions or your textbook;
• and only then look at the answers.
Good luck!
MAT2612 October/November 2016
INTRODUCTION TO DISCRETE MATHEMATICS
Duration : 2 Hours 100 Marks

1. Use mathematical induction to show that

n! > 2n
for all n ∈ N; n ≥ 4. [7]
Let P (n) be the statement that n! > 2n .
Basis step
For n = 4, 4! = 24 and 24 = 16 so 4! > 24 .
Induction hypothesis
Assume P (k) is true for some k ∈ N, k ≥ 4, i.e.
k! > 2k .
To prove P (k + 1) is true, i.e.

(k + 1)! > 2k+1 .

Proof
(k + 1)! = (k + 1)k!
> (k + 1)2k (by the induction hypothesis)
k
> 2·2 (since k + 1 > 2 for k ≥ 4)
k+1
= 2 .

Thus from mathematical induction n! > 2n for all n ∈ N; n ≥ 4.

3
 2. (a) How many distinguishable arrangements are there of the letters in the word “FULFILLING”?
(2)
There are 10 letters in “FULFILLING” and L occurs three times and both F and I occur twice.

10!
The number of distinguishable arrangements therefore are .
3!2!2!
(b) How many distinguishable arrangements are there of the letters in “FULFILLING” if the three Ls
are next to each other (i.e. LLL)? (3)
“Glue” the three Ls together. We now arrange 8 “letters”.

8!
The number of distinguishable arrangements are .
2!2!
[5]

3. Suppose Gauteng car number plates consist of three letters followed by three numbers. The allowable
letters are the 21 consonants (i.e. all the letters of the alphabet except A, E, I, O, U) and the allowable
numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Repetition of letters and numbers is allowed.

(a) How many different number plates are possible? (3)

Since repetition is allowed, the letters can be arranged in (21) ways and the numbers in (10)3
3

ways. Hence there are (21)3 × (10)3 possible number plates.

(b) How many different number plates will have exactly two adjacent numbers the same? (4)
There are 10 choices for the numbers that are adjacent. There are 2 positions in which the
numbers can be adjacent. The third position can be filled by one of 9 numbers. Thus there are

(21)3 × 10 × 2 × 9 such number plates.

(c) How many different number plates will have exactly two Rs? (3)
3


The two Rs can be in 2 = 3 positions. The other position can be filled by one of the remaining
20 consonants. Hence there are

3 × 20 × 103 such number plates.

(d) How many different number plates will have exactly two Rs and at least one 9? (4)
“At least one 9” is the complement of “no 9”.
If there is no 9, the numbers can be chosen from the remaining nine numbers. The number of
plates with exactly 2 Rs and no 9 is
3 × 20 × 93 .
Hence the number of plates with exactly two Rs and at least one 9 is

3 × 20 × 103 − 3 × 20 × 93 .

Alternatively
The number of plates with exactly 2 Rs and one 9 is 60 × 3 × 92 ;
The number of plates with exactly 2 Rs and two 9s is 60 × 3 × 9;
The number of plates with exactly 2 Rs and three 9s is 60. Hence the number of plates with
exactly 2 Rs and at least one 9 is

60 × 3 × 92 + 60 × 3 × 9 + 60 (= 60 × 271).

[14]

4
 MAT2612/102/3/2017

4. You must choose a committee of 8 people containing at least two men. There are 9 men and 11
women to choose from. How many such committees are there?

(a) Explain what is wrong with the following “solution”.

 
9
Since you must choose at least two men, choose them in ways. Now choose the remaining
2  
18
6 members of the committee from the remaining 18 people in ways. By the product rule
6
there are thus   
9 18
2 2
such committees. (3)
Overcounting:
For example choose
| man{z1 and man 2}. Then choose man 3 and 5 people from the remaining 17.
This is the same as choosing man
| {z man 3} and then man 2 and 5 people from the remaining
1 and
17.
(Also, the final answer indicates that only four people were chosen for the team instead of eight
people.)
(b) Give a correct solution. (5)
The complement of “at least two” is “at most one”, i.e. 0 or 1.
 
11
The number of committees with 0 men is 1 × .
8
  
9 11
The number of committees with 1 man is .
1 7
   
11 11
The number of committees with at most 1 man is +9 .
8 7
 
20
The total number of committees without restrictions is .
8
Hence the number of committees with at least 2 men is
     
20 11 11
− +9 .
8 8 7

[8]

5. In how many ways can you choose 16 chocolates from 7 different types of there are more than 16 of
every type except type 1, of which there is only one? [6]
If we do not choose type 1, we choose 16 chocolates from 6 types
     
6 + 16 − 1 21 21
= =
16 16 5

choices.
If we choose one of type 1, then we choose 15 chocolates from 6 types
     
6 + 15 − 1 20 20
= =
15 15 5

choices.

5
 Thus we can choose the chocolates in    
21 20
+
16 15
ways.
6. Use the pigeonhole principle to show that if you pick five numbers from the integers 1 to 8, then two
of them must add up to nine. [6]
Every number can be paired with another to sum to nine. There are four such pairs: the numbers 1
and 8, 2 and 7, 3 and 6, and 4 and 5. Each of the five numbers you choose belongs to one of those
four pairs.
Let the four pairs of numbers be the pigeonholes and the five numbers you pick be the pigeons. By the
pigeonhole principle, two of the numbers must be from the same pair. This implies that two numbers
will sum to 9.
7. Let A = {1, 2, 3, 4, 6} and define the relation R on A by
a
aRb if and only if is an integer.
b
6
For example, 6R3 since since = 2 is an integer.
3
(a) Write R as a set of ordered pairs. (3)
R = {(1, 1), (2, 1), (2, 2), (3, 1), (3, 3), (4, 1), (4, 2), (4, 4), (6, 1), (6, 2), (6, 3), (6, 6)}.
(b) Draw the directed graph of (A, R). (3)

4 6

2 3

(c) Give the in-degree and out-degree of 2. (2)

in-degree(2) = 3; and out-degree(2) = 2.
(d) Determine if (A, R) is a poset. Give complete reasoning. (7)
a +
R is reflexive since aRa for all a ∈ A because a = 1 ∈ Z .
R is antisymmetric. Suppose aRb and bRa. Then ab = n and ab = m, where n, m ∈ Z + . But then
a b
b × a = 1 = nm and hence n = m = 1 and so a = b.
R is transitive. Suppose aRb and bRc. Then ab = n and cb = m, where n, m ∈ Z + .
Hence ac = ab × cb = nm and nm ∈ Z + .
Hence aRc.
Since R is reflexive, antisymmetric and transitive (A, R) is a poset.
[You can also determine MR and use the properties of MR to answer (d).]

6
 MAT2612/102/3/2017

[15]

8. (a) Suppose f and g are functions whose domains are subsets of Z+ , the set of positive integers.
Give the definition of
“f is O(g)”. (2)

f is O(g) if and only if there exist constants c and k such that

|f (n)| ≤ c|g(n)| for all n ≥ k.

(b) Use the definition of “f is O(g)” to show that n2 + 27 is O(3n ). (4)

|2n + 27| = 2n + 27
= 2 n + 33
≤ 3n + 3 n for n ≥ 3
n
= 2|3 |.

Since |2n + 27| ≤ c|3n | for n ≥ k, where c = 2 and k = 3, it follows that 2n + 27 is O(3n ).
[6]

9. Consider the poset (A, R) represented by the following Hasse diagram.

a

b c d

e g
f

(a) Give each of the following. If any do not exist, explain clearly why.
(i) The greatest element of (A, R). (2)
a
(ii) The least element of (A, R). (2)
h
(iii) All upper bounds of {e, f }. (2)
a, b, c
(iv) The least upper bound (LUB) of {e, f }. (2)
None since there is no element with paths up to all the other elements.

7
 (v) All lower bounds of {b, d}. (2)
f, h
(vi) The greatest lower bound (GLB) of {b, d}. (2)
f
(vii) A complement of b. (2)
Since {e, f } does not have a LUB, (A, R) is not a lattice and therefore b does not have a
complement. (A complement is only defined if (A, R) is a lattice.)
(viii) A complement of f . (2)
None since (A, R) is not a lattice.
(ix) Any two incomparable elements. (2)
b and c
(b) Give complete reasons for answers to the following.
(i) Is (A, R) a lattice? (2)
No, since not every pair of elements has GLB and a LUB, e.g. {e, f } does not have a LUB.
(ii) Is (A, R) a complemented lattice? (2)
No, (A, R) is not a lattice.
(iii) Is (A, R) a Boolean algebra? (2)
No, since it is not a (complemented) lattice.
[24]

10. Let  
1 2 3 4 5 6 7 8
p=
3 8 5 6 1 2 4 7
and  
1 2 3 4 5 6 7 8
q=
1 8 6 7 2 3 4 5

(a) Determine whether p is an even or odd permutation by writing p as a product (composition) of

transpositions. (5)

(1, 3, 5) ◦ (2, 8, 7, 4, 6)
= (1, 5) ◦ (1, 3) ◦ (2, 6) ◦ (2, 4) ◦ (2, 7) ◦ (2, 8).

It follows that p is an even permutation.

(b) Determine the compositions
(i) p ◦ q.
(ii) q ◦ p.

Write the compositions in the form

 
1 2 3 4 5 6 7 8
. (4)
− − − − − − − −

8
 MAT2612/102/3/2017

(i)  
1 2 3 4 5 6 7 8
p◦q =
3 7 2 4 8 5 6 1
(ii)  
1 2 3 4 5 6 7 8
q◦p=
6 5 2 3 1 8 7 4
[9]

TOTAL: [100]

c
UNISA 2016