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