Semester One Final Examinations, 2018
MATH1061 Discrete Mathematics
This exam paper must not be removed from the venue
Seat Number Student Number Family Name First Name
____________________ ________ |__|__|__|__|__|__|__|__| _____________________ _____________________
School of Mathematics & Physics EXAMINATION
Semester One Final Examinations, 2018
MATH1061 Discrete Mathematics
This paper is for St Lucia Campus and St Lucia Campus (External) students.
Examination Duration:
Reading Time:
Exam Conditions:
This is a Central Examination
This is a Closed Book Examination – specified materials permitted During reading time – write only on the rough paper provided
This examination paper will be released to the Library
120 minutes 10 minutes
For Examiner Use Only
Question Mark 1
Materials Permitted In The Exam Venue:
(No electronic aids are permitted e.g. laptops, phones) 6
Calculators – Casio FX82 series or UQ approved (labelled)
Materials To Be Supplied To Students:
Instructions To Students:
Additional exam materials (eg. answer booklets, rough paper) will be
provided upon request. 11
Complete all examination questions in the space provided on this examination paper. If more space is required, use the backs of pages. The final page is a formula sheet, which you may detach. Nothing written on the formula sheet will be marked.
Total ________ Out of 70
Page 1 of 15
Semester One Final Examination, 2018 MATH1061 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
∼ ((p → q) ∧ (p → r)) ≡ p ∧ (∼ q ∨ ∼ r).
Page 2 of 15
Semester One Final Examination, 2018 MATH1061 Discrete Mathematics
2. Consider the sequence defined recursively as
a1 =2, a2 =3, a3 =4 and ak =ak−1 +ak−2 +ak−3 forallintegersk≥4.
Prove that an ≤ 2n for each integer n ≥ 1.
Page 3 of 15
Semester One Final Examination, 2018 MATH1061 Discrete Mathematics
3. Indicate whether each of the following statements is true or false, by circling True or False as appropriate. No explanation is required.
(a) Z ∈ Q.
True False
(b) ∀ sets A, ∅ ∈ A.
True False
(c) If A = {∅} then |P(A)| = 2. True False
(d) ∀ sets A and B, if |A| = |B| then every one-one function f : A → B is an onto function. True False
(e) If A = {a,b,c} and B = {d,e} then f = {(a,d),(b,d),(c,d)} is a function from A to B. True False
(f) Let A be a non-empty set, and let ρ be a relation defined on P(A) where ∀X,Y ∈ P(A), XρY ifandonlyifX∩Y ̸=∅.
(i) ρ is reflexive.
True False
(ii) ρ is symmetric.
True False
(iii) ρ is transitive.
True False
(g) (Z+,×) is a group, where × represents multiplication. True False
(h) Let A = {1,2,3,4}. The set of all functions from A to A with the binary operation of composition of functions is a group.
True False
Page 4 of 15
Semester One Final Examination, 2018 MATH1061 Discrete Mathematics
4. Prove the following statement. For all sets A and B, P(A) ⊆ P(B) if and only if A ⊆ B.
Page 5 of 15
Semester One Final Examination, 2018 MATH1061 Discrete Mathematics
5. Prove that the set Z+ × Z+ × Z+ × Z+ is countable.
Page 6 of 15
Semester One Final Examination, 2018 MATH1061 Discrete Mathematics
6. For each positive integer x, define d(x) to be the number of positive divisors of x. Let ρ be the relation on Z+ defined as follows: ∀m, n ∈ Z+, (m, n) ∈ ρ if and only if d(m) ≤ d(n).
(a) Explain why (1,n) ∈ ρ for all n ∈ Z+.
(b) Prove or disprove the following statement: the relation ρ is reflexive.
(c) Prove or disprove the following statement: the relation ρ is symmetric.
(d) Prove or disprove the following statement: the relation ρ is anti-symmetric.
(e) Prove or disprove the following statement: the relation ρ is transitive.
Page 7 of 15
Semester One Final Examination, 2018
MATH1061 Discrete Mathematics
7. (a) List the cyclic subgroups of (Z3 × Z3, +).
(b) Explain why (Z3 × Z3, +) is not isomorphic to (Z9, +).
Page 8 of 15
Semester One Final Examination, 2018 MATH1061 Discrete Mathematics
8. Solve the equation 12x + 15 = 11 in the field (Z53, +, ·). Hence determine the smallest positive integer y such that 12y + 15 ≡ 11 (mod 53).
(Hint: 12×31=7×53+1.)
Page 9 of 15
Semester One Final Examination, 2018 MATH1061 Discrete Mathematics
9. Consider a standard deck of cards having 52 cards, that is, 13 cards (Ace, 2, 3, . . . , 10, Jack, Queen, King) of each suit (Hearts, Diamonds, Spades and Clubs).
(a) Determine the number of sets of four cards that can be selected from the deck of 52 cards. (You do not need to simplify your answer.)
(b) If four cards are chosen at random from the deck, what is the probability that the four cards are all hearts? (You do not need to simplify your answer. )
(c) Determine the number of sets of four cards that can be selected from the deck such that the four cards include at least one Ace or at least one 2 (where ‘or’ means ‘inclusive or’). (You do not need to simplify your answer.)
Page 10 of 15
Semester One Final Examination, 2018 MATH1061 Discrete Mathematics
10. Determine the smallest integer n such that if A is any subset of cardinality n chosen from the set S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13} then A contains at least two integers whose difference is divisible by 3. Explain your answer clearly including a justification that your integer n is as small as possible.
Page 11 of 15
Semester One Final Examination, 2018 MATH1061 Discrete Mathematics
11. Use the Binomial Theorem to calculate the coefficient of x9 in the expansion of (2×3 − 5)10. (You do not need to simplify your answer.)
Page 12 of 15
Semester One Final Examination, 2018 MATH1061 Discrete Mathematics
12. Let T be a tree with 8 edges that has exactly 5 vertices of degree 1. Prove that if v is a vertex of maximum degree in T , then 3 ≤ deg(v) ≤ 5.
Page 13 of 15
Semester One Final Examination, 2018 MATH1061 Discrete Mathematics
13. For each of the following lists of conditions, either draw a graph with the stated properties or explain why no such graph exists.
(a) A graph with 5 vertices and 3 edges.
(b) A graph with 6 vertices of which 3 have degree 3 and 3 have degree 2.
(c) An Eulerian graph with 5 vertices and 7 edges.
(d) A tree having 5 vertices and degree sequence 3,2,2,2,1.
END OF EXAMINATION
Page 14 of 15
Semester One Final Examination, 2018 MATH1061 Discrete Mathematics
Logical Equivalences
MATH1061/MATH7861 Examination Formula Page
Given any statement variables p, q and r, a tautology t and a contradiction c, the following logical
equivalences hold.
Commutative laws Associative laws Distributive laws Identity laws Negation laws Double negative laws Idempotent laws Universal bound laws De Morgan’s laws Absorption laws Negations of t and c
Valid Argument Forms
p∧q≡q∧p (p∧q)∧r≡p∧(q∧r) p∧(q∨r)≡(p∧q)∨(p∧r) p∧t≡p
∼ (∼ p) ≡ p
∼ (p ∧ q) ≡∼ p ∨ ∼ q
p ∨ (p ∧ q) ≡ p
p→q p∼q∼p ∴q∴p∴q
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) p∨c≡p
p∧c≡c ∼(p∨q)≡∼p∧∼q p∧(p∨q)≡p ∼c≡t
Generalization (a)
Elimination
p ∧ q ∴p∴q∴r
p Contradiction Rule ∼ p → c q∴p ∴p∧q
Transitivity p→q q→r
∴p→r Proofby p∨q
Specialization Conjunction
(b) p ∧ q q→r
∴p∨q divisionintocases p→r
Set Identities For all sets A, B and C that are subsets of a universal set U:
1. Commutative Laws 2. Associative Laws
3. Distributive Laws
4. Identity Laws
5. Complement Laws
6. Double Complement Law 7. Idempotent Laws
8. Universal Bound Laws
9. De Morgan’s Laws
10. Absorption Laws
11. Complement of U and ∅ 12. Set Difference Law
(a)A∪B=B∪A (b)A∩B=B∩A (a)(A∪B)∪C=A∪(B∪C)
(b) (A ∩ B) ∩ C = A ∩ (B ∩ C) (a)A∪(B∩C)=(A∪B)∩(A∪C)
(b) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) (a)A∪∅=A (b)A∩U=A (a)A∪Ac =U (b)A∩Ac =∅ (Ac)c = A
(a)A∪A=A (b)A∩A=A
(a)A∪U=U (b)A∩∅=∅
(a)(A∪B)c =Ac ∩Bc (b)(A∩B)c =Ac ∪Bc (a)A∪(A∩B)=A (b)A∩(A∪B)=A (a)Uc =∅ (b)∅c =U
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 p ,p ,…,p , and positive integers e ,e ,…,e such that n = pe1pe2 ···pek,
12k 12k 12k 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- For all sets A and B, if |A| ≤ |B| and |A| ≥ |B| then |A| = |B|.
Page 15 of 15