discrete mathematics exams need to solution and answer.
sehj
17R-T1-MATH1240-FinalExam-FINAL.pdf
UNIVERSITY OF MANITOBA
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.
END OF EXAM
DATE: 2017-01-16
DEPARTMENT & COURSE NO: MATH 1240
EXAMINATION: Elementary Discrete Mathematics
UNIVERSITY OF MANITOBA
FINAL EXAM
PAGE: 12 of 13
TIME: 3 hours
EXAMINER: Borgersen
SCRAP PAPER
DATE: 2017-01-16
DEPARTMENT & COURSE NO: MATH 1240
EXAMINATION: Elementary Discrete Mathematics
UNIVERSITY OF MANITOBA
FINAL EXAM
PAGE: 13 of 13
TIME: 3 hours
EXAMINER: Borgersen
SCRAP PAPER
