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
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:
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

Email:51zuoyejun

@gmail.com