Semester Two Final Examinations, 2019 MATH7861 Discrete Mathematics

Page 1 of 17

This exam paper must not be removed from the venue

School of Mathematics & Physics

EXAMINATION

Semester Two Final Examinations, 2019

MATH7861 Discrete Mathematics

This paper is for St Lucia Campus students.

Examination Duration: 120 minutes

Reading Time: 10 minutes

Exam Conditions:

This is a Central Examination

This is a Closed Book Examination - no materials permitted

During reading time - write only on the rough paper provided

This examination paper will be released to the Library

Materials Permitted In The Exam Venue:

(No electronic aids are permitted e.g. laptops, phones)

Calculators - Casio FX82 series or UQ approved (labelled)

Materials To Be Supplied To Students:

None

Instructions To Students:

Additional exam materials (eg. answer booklets, rough paper) will be

provided upon request.

Answer all questions in the space provided. Show all working; answers given

without justification may not receive full marks. Questions carry the number of

marks shown.

Total marks available: 70

Venue ____________________

Seat Number ________

Student Number |__|__|__|__|__|__|__|__|

Family Name _____________________

First Name _____________________

For Examiner Use Only

Question Mark

1 /3

2 /6

3 /6

4 /6

5 /6

6 /10

7 /4

8 /10

9 /9

10 /10

Total ________

Semester Two Final Examination, 2019 MATH7861 Discrete Mathematics

Answer each question in the space provided on this examination paper, using the backs of pages if

more space is required. Each question is worth the number of marks indicated on the right.

1. For statement variables p, q and r, prove that

(⇠(q !⇠p) ^ r) _ (⇠(p! q) ^ r) ⌘ p ^ r.

(3 marks)

Page 2 of 17

Semester Two Final Examination, 2019 MATH7861 Discrete Mathematics

2. Let a = p2q7r4 and let b = p3q4s where p, q, r and s are primes with p < q < r < s.

(a) What is the greatest common divisor of a and b? (No explanation required).

(2 marks)

(b) What is the least common multiple of a and b? (No explanation required).

(2 marks)

(c) What is the smallest positive integer n such that nab is a perfect square? (Recall that an

integer x is a perfect square if and only if there exists an integer y such that x = y2.) (No

explanation required).

(2 marks)

Page 3 of 17

Semester Two Final Examination, 2019 MATH7861 Discrete Mathematics

3. Let a0, a1, a2, . . . be the sequence defined by the explicit formula

an = 7 · 3n + 5 · (2)n

for each integer n 0.

(a) Show that this sequence satisfies the recurrence relation ak = ak1 + 6ak2 for all integers

k 2.

(4 marks)

(b) State a recursive definition for this sequence.

(2 marks)

Page 4 of 17

Semester Two Final Examination, 2019 MATH7861 Discrete Mathematics

4. (a) Prove, using mathematical induction, that 4k ⌘ 4 (mod 6) for each positive integer k.

(3 marks)

(b) Prove that 2n ⌘ 2 (mod 6) for each odd positive integer n.

(3 marks)

Page 5 of 17

Semester Two Final Examination, 2019 MATH7861 Discrete Mathematics

5. Recall that ; denotes the empty set. Sets A, B, C, D, E, F are given by

A = Z, B = Q, C = {1,p2, 75 , ;}, D = ;, E = {;, B}, F = {B}.

Complete the following (and remember to write curly braces where appropriate).

(6 marks)

(a) A \ C =

(b) B \ C =

(c) C [D =

(d) P(C \ E) =

(e) E ⇥ F =

(f) E F =

Page 6 of 17

Semester Two Final Examination, 2019 MATH7861 Discrete Mathematics

6. Recall that for real numbers a, b with a < b, we define the intervals (a, b) = {x 2 R | a < x < b}

and (a, b ] = {x 2 R | a < x b}.

(a) State a bijection f : (2, 3)! (5, 8).

(2 marks)

(b) Prove that your function f from part (a) is indeed a bijection from (2, 3) to (5, 8).

(5 marks)

Page 7 of 17

Semester Two Final Examination, 2019 MATH7861 Discrete Mathematics

6. (c) State a bijection g : (0, 1)! (0, 1 ]. No explanation required.

(3 marks)

Page 8 of 17

Semester Two Final Examination, 2019 MATH7861 Discrete Mathematics

7. Define a relation ⇢ on R by

x⇢y if and only if x+ y 2 Q.

(a) Determine whether ⇢ is reflexive, whether ⇢ is symmetric, and whether ⇢ is transitive. For

each property, explain why or why not.

(3 marks)

(b) Let A = {1, 2, 3} and define a relation ⌧ on P(A) by

X ⌧ Y if and only if X ✓ Y.

Is ⌧ a partial order relation? Answer yes or no. No explanation required.

(1 mark)

Page 9 of 17

Semester Two Final Examination, 2019 MATH7861 Discrete Mathematics

8. (a) In a federal election, there are five people competing to become your local representative.

To vote, you must write the numbers 1–5 inclusive on the ballot paper, one beside each

name. An example is shown below.

3 Artem

5 Barbara

1 Cecilia

2 Darryn

4 Ell

In how many ways could you cast a vote? Give your answer as a single integer.

(2 marks)

(b) In a state election, there are again five people competing to become your local representative.

This time, you can vote for k candidates for any 0 k 5. To do this, you must write the

numbers 1, . . . , k beside your k chosen candidates, and you must leave the remaining boxes

blank. An example is shown below.

3 Artem

2 Barbara

Cecilia

Darryn

1 Ell

In how many ways could you cast a vote? Give your answer as a single integer.

(3 marks)

Page 10 of 17

Semester Two Final Examination, 2019 MATH7861 Discrete Mathematics

8. (c) What is the coecient of x3 in (2 3x)5 ? Give your answer as a single integer.

(2 marks)

(d) How many onto functions are there from Z5 to Z2? Give your answer as a single integer.

(3 marks)

Page 11 of 17

Semester Two Final Examination, 2019 MATH7861 Discrete Mathematics

9. (a) Which of the following are groups? You do not need to show your working.

i) (Q {0},⇥)

ii) (Q {0},÷)

iii) ({true, false},^)

iv) (E,+), where E is the set of all even integers.

(2 marks)

(b) Let (G, ) be a group. Explain what it means for (H, ) to be a subgroup of (G, ).

You do not need to explain what a group is.

(1 mark)

Page 12 of 17

Semester Two Final Examination, 2019 MATH7861 Discrete Mathematics

9. (c) Write out the full Cayley table for (Z5 {0},⇥).

(2 marks)

Page 13 of 17

Semester Two Final Examination, 2019 MATH7861 Discrete Mathematics

9. (d) Recall that the symbol Q+ represents all positive rationals. Is the group (Z,+) isomorphic

to the group (Q+,⇥)? Explain why / why not.

(4 marks)

Page 14 of 17

Semester Two Final Examination, 2019 MATH7861 Discrete Mathematics

10. (a) Which of the following graphs contain an Euler circuit?

(i) (ii) (iii)

You do not need to show your working.

(3 marks)

(b) A graph G has precisely six vertices and eight edges. Five of the vertices have degree 3.

What is the degree of the remaining vertex?

(2 marks)

(c) Is it possible to have a simple graph G with precisely six vertices and eight edges, where

five of the vertices have degree 2? Explain why / why not.

(2 marks)

Page 15 of 17

Semester Two Final Examination, 2019 MATH7861 Discrete Mathematics

10. (d) Suppose you wish to partition the positive integers Z+ into two sets A,B. Show that, no

matter how you do this, one of the sets A or B must contain two elements n,m whose

di↵erence nm is a prime number.

(3 marks)

END OF EXAMINATION

Page 16 of 17

Semester Two Final Examination, 2019 MATH7861 Discrete Mathematics

MATH1061/MATH7861 Examination Formula Page

Logical Equivalences

Given any statement variables p, q and r, a tautology t and a contradiction c, the following logical

equivalences hold.

Commutative laws p ^ q ⌘ q ^ p p _ q ⌘ q _ p

Associative laws (p ^ q) ^ r ⌘ p ^ (q ^ r) (p _ q) _ r ⌘ p _ (q _ r)

Distributive laws p ^ (q _ r) ⌘ (p ^ q) _ (p ^ r) p _ (q ^ r) ⌘ (p _ q) ^ (p _ r)

Identity laws p ^ t ⌘ p p _ c ⌘ p

Negation laws p_ ⇠ p ⌘ t p^ ⇠ p ⌘ c

Double negative laws ⇠ (⇠ p) ⌘ p

Idempotent laws p ^ p ⌘ p p _ p ⌘ p

Universal bound laws p _ t ⌘ t p ^ c ⌘ c

De Morgan’s laws ⇠ (p ^ q) ⌘⇠ p_ ⇠ q ⇠ (p _ q) ⌘⇠ p^ ⇠ q

Absorption laws p _ (p ^ q) ⌘ p p ^ (p _ q) ⌘ p

Negations of t and c ⇠ t ⌘ c ⇠ c ⌘ t

Set Identities For all sets A, B and C that are subsets of a universal set U :

1. Commutative Laws (a) A [ B = B [ A (b) A \ B = B \ A

2. Associative Laws (a) (A [ B) [ C = A [ (B [ C)

(b) (A \ B) \ C = A \ (B \ C)

3. Distributive Laws (a) A [ (B \ C) = (A [B) \ (A [ C)

(b) A \ (B [ C) = (A \ B) [ (A \ C)

4. Identity Laws (a) A [ ; = A (b) A \ U = A

5. Complement Laws (a) A [ Ac = U (b) A \ Ac = ;

6. Double Complement Law (Ac)c = A

7. Idempotent Laws (a) A [ A = A (b) A \ A = A

8. Universal Bound Laws (a) A [ U = U (b) A \ ; = ;

9. De Morgan’s Laws (a) (A [ B)c = Ac \Bc (b) (A \ B)c = Ac [ Bc

10. Absorption Laws (a) A [ (A \ B) = A (b) A \ (A [ B) = A

11. Complement of U and ; (a) U c = ; (b) ;c = U

12. Set Di↵erence Law A B = A \ Bc

The Quotient-Remainder Theorem Given any integer n and any positive integer d, there exist

unique integers q and r such that n = dq + r and 0 r < d.

Unique Factorisation Theorem Given any integer n > 1, there exists a positive integer k,

distinct prime numbers p1, p2, . . . , pk, and positive integers e1, e2, . . . , ek such that n = p

e1

1 p

e2

2 · · · pekk ,

and any other expression for n as a product of prime numbers is identical to this except perhaps for

the order in which the factors are written.

Schro¨der-Bernstein Theorem For all sets A and B, if |A| |B| and |A| |B| then |A| = |B|.

Binomial Theorem Given any real numbers a and b, and any nonnegative integer n,

(a+ b)n =

nX

k=0

✓

n

k

◆

ankbk.

Page 17 of 17