Discrete math final exam answers

Discrete Mathematics

DEPARTMENT OF MATHEMATICS

MATH 1240 Elementary Discrete Mathematics

FINAL EXAM

2017-01-16 3:30pm

FAMILY / LAST NAME: (Print in ink)

FIRST NAME: (Print in ink)

STUDENT NUMBER:

SIGNATURE: (in ink)

(I understand that cheating is a serious offense)

INSTRUCTIONS TO STUDENTS:

This is a 3 hour exam.

Fill in all the information above. No calculators, texts,

notes, cell phones, pagers, translators or other

electronics are permitted. No outside paper is permitted.

This exam has a title page and 13 other pages, 2 of

which can be used for rough work. You may remove the

scrap pages if you like, but be careful not to loosen the

staple. Please check that you have all pages.

Work done on the back of pages will not be

marked. If you need more room for any question, write

your solution on one of the scrap pages, and clearly

indicate in the original question where to find your

solution.

There are 20 questions for a total of 120 marks.

Show all your work clearly and justify your answers

using complete sentences (unless it is explicitly stated

that you do not have to do that). Unjustified answers

may receive LITTLE or NO CREDIT.

If a question calls for a specific method, no credit will be

given for other methods.

DATE: 2017-01-16

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA

FINAL EXAM

PAGE: 1 of 13

TIME: 3 hours

EXAMINER: Borgersen

Definitions

1. Define each of the following as we have defined them in class. Proper notation and grammar may be marked.

(a)[2] Contrapositive

(b)[2] Function (as a type of relation)

(c)[2] Equivalence Relation

(d)[2] Irreflexive Relation

2.[2] Fill in the blanks: A graph G (as we have defined in this course) is an ordered pair G = (V,E) where V is a non-empty set, and E is a binary relation that is:

1) , and 2) .

3.[3] Let A = {1, x}, B = {2, y}, and let T = {(1, y), (x, 2)}. Then circle which of the following correctly describe T , and cross out which of the following do not describe T .

Binary Relation Function One-to-one function

Onto Function Bijection Sequence

Permutation Partition Binary Operation

Reflexive Relation Symmetric Relation Transitive Relation

Irreflexive Relation Anti-symmetric Relation

DATE: 2017-01-16

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA

FINAL EXAM

PAGE: 2 of 13

TIME: 3 hours

EXAMINER: Borgersen

Computation/ Calculation Questions

Sentences are not required for this section.

4.[4] Find [100]−1 in Z1009.

5. In a recent survey people were asked if they took a vacation in the summer, winter, or spring in the past year. The results were:

• 73 took a vacation in the summer • 51 took a vacation in the winter • 27 took a vacation in the spring • 2 took no vacation • 10 took vacations at all three times

• 33 took both a summer and a winter vaca- tion

• 18 took only a winter vacation

• 5 took summer and spring vacations but no winter vacations

Let S be the set of those who took vacation in the summer, W the set of those who took vacation in the winter, and P the set of those who took vacation in the spring.

(a)[6] Fill in the regions of the following Venn diagram with the number of people in that region:

(b)[2] How many people in total were surveyed?

(c)[2] How many people took vacations exactly two times of the year?

(d)[2] How many people took vacations during at most one time of the year?

(e)[1] What percentage of all the people had taken vacations during both summer and winter but not spring? (Express your answer as a fraction)

DATE: 2017-01-16

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA

FINAL EXAM

PAGE: 3 of 13

TIME: 3 hours

EXAMINER: Borgersen

Short Answer

For these questions, work and sentences are not necessary unless indicated in the question.

6.[2] Negate the following:

∀X ∃Y ∃C ∀Z p

7.[2] Let A = {a, b, c}. Write out all the elements of P(A).

8.[5] Fill in the following truth-table:

S1 = p → q S2 = ¬q → p S3 = q → p

S4 = ¬(p ∧ ¬q) S5 = ¬(p ∨ q) S6 = p ∨ ¬q

p q p ∨ q ¬q p ∧ ¬q S1 S2 S3 S4 S5 S6 0 0

0 1

1 0

1 1

Which of the propositions S1, . . . , S6 are logically equivalent to each other?

DATE: 2017-01-16

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA

FINAL EXAM

PAGE: 4 of 13

TIME: 3 hours

EXAMINER: Borgersen

9.[6] Prove the following argument, stating justification for each step below:

p → r ¬p → q q → s ¬r → s

1) p → r Premise

2) ¬p → q Premise

3) q → s Premise

4)

5)

6)

10.[6] Simplify (p ∨ q) ∧ ¬(¬p ∧ q). Show all your steps.

11. Name 3 elements in each of the following sets:

(a)[2] S1 = { r ∈ Q+ : r = a

b , b ≥ 3, b ∈ Z+, a ∈ 5Z

}

(b)[2] S2 =

{ x ∈ R : x < 1

2 , x ̸∈ Q

}

DATE: 2017-01-16

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA

FINAL EXAM

PAGE: 5 of 13

TIME: 3 hours

EXAMINER: Borgersen

12. For each of the following collection of properties, draw one graph G that satisfies them all:

(a)[2] G is Bipartite and contains a vertex of degree 3

(b)[2] G is a non-planar graph with ∆(G) ≤ 3

(c)[2] G is a tree with 5 vertices and ∆(G) = 4.

(d)[0] BONUS 2 MARKS: G is a non-planar graph with δ(G) = 1

DATE: 2017-01-16

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA

FINAL EXAM

PAGE: 6 of 13

TIME: 3 hours

EXAMINER: Borgersen

13.[8] Consider the following graph:

(a) Is this graph simple? Explain why.

(b) What is the degree set for this graph? Write the degrees in increasing order.

(c) Find an example of each of the following in the above graph, or explain why they do not exist:

i. Euler Trail (aka an Euler Circuit)

ii. semi-Eulerian Trail

DATE: 2017-01-16

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA

FINAL EXAM

PAGE: 7 of 13

TIME: 3 hours

EXAMINER: Borgersen

Proofs

Reminder: All proofs must be well-written and may be marked based on sentence structure, proper notation, and grammar.

14.[7] Prove if f : A → B and g : B → C are both 1:1 functions, then g ◦ f : A → C is also 1:1.

15.[8] Let a, b ∈ Z+, d = gcd(a, b). Prove that gcd ( a

d , b

d

) = 1.

DATE: 2017-01-16

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA

FINAL EXAM

PAGE: 8 of 13

TIME: 3 hours

EXAMINER: Borgersen

16. (a)[6] Let G be a graph, k ∈ Z+, k ≥ 2. Prove that if δ(G) = k, then G contains a cycle of length at least k + 1.

(b)[4] Use the fact in part (a) to prove that every tree contains a vertex of degree 1.

DATE: 2017-01-16

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA

FINAL EXAM

PAGE: 9 of 13

TIME: 3 hours

EXAMINER: Borgersen

17. Let R be an equivalence relation on a set X. Prove that: (a)[4] ∀x, x ∈ [x]

(b)[4] ∀x, y ∈ X, if [x] = [y], then xRy.

18.[8] Prove the infinite pigeonhole principle, that is, let S be an infinite set, n ∈ Z+. Prove that no matter how the elements of S are partitioned into n parts, at least one of the parts must be infinite.

DATE: 2017-01-16

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA

FINAL EXAM

PAGE: 10 of 13

TIME: 3 hours

EXAMINER: Borgersen

19.[10] Suppose that a1 = a2 = 1 and for every n ≥ 1, an+2 = 3an+1 + an. Prove by induction that for all n ≥ 1, gcd(an, an+1) = 1. Write your proof clearly, and in good style. The statements Pn are already defined for you.

Proof. For all n ≥ 1, let Pn denote the statement that gcd(an, an+1) = 1...

DATE: 2017-01-16

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA

FINAL EXAM

PAGE: 11 of 13

TIME: 3 hours

EXAMINER: Borgersen

20.[0] BONUS: MAX 6 MARKS Prove that the real interval (0, 1) is not countably infinite.

Marks will only be given for substantial well-written progress towards the proof.