- July 3, 2020

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 = ak 1 + 6ak 2 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 coe cient 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 n m 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 ◆ an kbk. Page 17 of 17