discrete mathematics exams need to solution and answer.

UNIVERSITY OF MANITOBA

DEPARTMENT OF MATHEMATICS

MATH 1240 Elementary Discrete Mathematics

FINAL EXAM

2017-04-30 12:00pm

FAMILY / LAST NAME: (Print in ink)

FIRST NAME: (Print in ink)

STUDENT NUMBER:

SIGNATURE: (in ink)

(I understand that cheating is a serious offense)

Please indicate your instructor and section by checking the appropriate box

below:

A01 MWF (12:30pm – 1:20pm) R. Borgersen

Deferred

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 14 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.

There are 17 questions for a total of 131 marks.

Important: Any work you want marked must be written on the front of a

page. If you need more room, write your answers on the front of the scrap

paper (and be sure to indicate that your work is continued). Anything

written on the back of pages will not be marked (so feel free to use these

for rough work).

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-04-30

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA FINAL EXAM

PAGE: 1 of 14

TIME: 3 hours

EXAMINER: Borgersen

Throughout the exam, you may use the following fact without proof: For finite

sets A, B with |A| = m, |B| = n, the number of onto functions from A to B is

n−1∑ k=0

(−1)k (

n

n− k

) (n− k)m.

Definitions

1. Define each of the following terms:

(a)[3] DeMorgan’s Laws for two primitive statements p and q say...

(b)[3] For two sets A and B, the Cartesian product A×B is...

(c)[3] For a, b ∈ Z, m ∈ Z+, “a ≡ b mod(m)” means...

(d)[3] A binary operation on a set A is...

DATE: 2017-04-30

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA FINAL EXAM

PAGE: 2 of 14

TIME: 3 hours

EXAMINER: Borgersen

(e)[3] A relation on A is anti-symmetric if...

(f)[3] A graph is planar if...

(g)[3] A partition of a set X is...

Short Answer

For the questions in this section, no justification is necessary.

2.[8] Let p(x), q(x) denote the following open statements:

p(x) : x ≤ 3 q(x) : x+ 1 is odd

If the universe consists of all integers, circle which of the following are TRUE

and cross out the ones that are FALSE:

q(1) ¬p(3) p(7) ∨ q(7)

p(3) ∧ q(4) ¬(p(−4) ∨ q(−3))

¬p(−4) ∧ ¬q(−3) ∃x [p(x) ∧ q(x)] ∀x q(x)

DATE: 2017-04-30

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA FINAL EXAM

PAGE: 3 of 14

TIME: 3 hours

EXAMINER: Borgersen

3. Let A = {1, 2, 3}, B = {2, 4, 5}, C = {x, y, z, w}. (a)[2] How many relations from A to B contain (1, 2) and (1, 5)?

(b)[2] How many one-to-one functions f are there such that f : A → C?

(c)[2] How many functions f are there such that f : C → A and f(x) = 2?

(d)[2] How many closed binary operators on A are there?

(e)[3] How many functions f are there such that f : A → C and |f(A)| = 2?

DATE: 2017-04-30

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA FINAL EXAM

PAGE: 4 of 14

TIME: 3 hours

EXAMINER: Borgersen

4.[3] Find the smallest value for a such that 2a is a perfect square and 3a is a

perfect cube.

5.[3] Give examples of three non-empty distinct relationsR1,R2,R3 fromA = {1, 2, 3} to B = {Red,Green,Blue}.

6. Draw each of the following graphs:

(a)[2] K2,5

(b)[2] G where V (G) = {1, 2, 3, 4, 5} and E(G) = {{x, y} : x ≡ y mod 3}

(c)[2] G where V (G) = P({1, 2}) and E(G) = {{A,B} : A ∩B = ∅}

DATE: 2017-04-30

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA FINAL EXAM

PAGE: 5 of 14

TIME: 3 hours

EXAMINER: Borgersen

Long Answer

7.[5] In how many ways can the symbols a,b,c,x,x,x,x be arranged so that no x

is adjacent to another x? Explain (in complete sentences).

8.[4] Construct a truth table for the following compound statement:

p → (q → r)

p q r

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

DATE: 2017-04-30

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA FINAL EXAM

PAGE: 6 of 14

TIME: 3 hours

EXAMINER: Borgersen

9. Consider the following graph G:

(a)[2] Find an open trail in G starting from A that is not a path.

(b)[2] Find a closed walk in G starting from A that is not a trail.

(c)[2] Is G planar? Justify your answer.

(d)[4] How many paths are there from A to H in G? Justify your answer.

DATE: 2017-04-30

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA FINAL EXAM

PAGE: 7 of 14

TIME: 3 hours

EXAMINER: Borgersen

10. Consider the following graph G:

(a)[2] What is δ(G)? What is ∆(G)? What is χ(G)?

δ(G) = ∆(G) = χ(G) =

(b)[2] Does G have an Euler circuit (that is, an Eulerian Trail)? If so, find it.

If not, justify why not.

(c)[2] Does G have a Hamilton cycle? If so, find it. If not, justify why not.

(d)[2] Is G bipartite? Justify your answer.

DATE: 2017-04-30

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA FINAL EXAM

PAGE: 8 of 14

TIME: 3 hours

EXAMINER: Borgersen

Proofs

11.[10] Prove using Mathematical Induction that for all n ≥ 1, n(n + 1)(n + 2) is divisible by 6. No marks will be awarded for any other method.

DATE: 2017-04-30

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA FINAL EXAM

PAGE: 9 of 14

TIME: 3 hours

EXAMINER: Borgersen

12.[6] Let A be a set, let F be a binary operation on A.

(a) Define what it means for e ∈ A to be an identity for F .

(b) Assume e1 and e2 are two identities for F . Prove that e1 = e2.

13.[8] Let A = Z+ and let f : P(A)×P(A) → P(A) be defined by f(X,Y ) = X∩Y . (a) Prove or disprove: f is onto.

(b) Prove or disprove: f is one-to-one.

DATE: 2017-04-30

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA FINAL EXAM

PAGE: 10 of 14

TIME: 3 hours

EXAMINER: Borgersen

14.[10] Prove that there are infinitely many primes.

DATE: 2017-04-30

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA FINAL EXAM

PAGE: 11 of 14

TIME: 3 hours

EXAMINER: Borgersen

15.[10] Let R be an equivalence relation on a set A. Prove that ∀x, y ∈ A, xRy if and only if [x] = [y].

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

DATE: 2017-04-30

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA FINAL EXAM

PAGE: 12 of 14

TIME: 3 hours

EXAMINER: Borgersen

17. Bonus Question. Rob thinks he has found a bijection between Z+ and {x ∈ R : 0 < x < 1}. His function F proceeds as follows: for each integer, map it to it’s “mirror image” between 0 and 1 in the following way:

F (1) = 0.1, F (2) = 0.2, F (3) = 0.3, F (10) = 0.01, ...

F (100) = 0.001, F (1000) = 0.0001, F (1234) = 0.4321, ...

(a)[0] Bonus (Max 1 Mark). Prove F is not onto by finding a fraction in

(0, 1) that is not mapped on to by this function. Justify your answer.

(b)[0] Bonus (Max 3 Marks). Prove F is not onto using Cantor’s Diagonal-

ization Argument (as done in class) to construct a real number in (0, 1)

that is not mapped on to by the function.

END OF EXAM

DATE: 2017-04-30

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA FINAL EXAM

PAGE: 13 of 14

TIME: 3 hours

EXAMINER: Borgersen

SCRAP PAPER

DATE: 2017-04-30

DEPARTMENT & COURSE NO: MATH 1240

EXAMINATION: Elementary Discrete Mathematics

UNIVERSITY OF MANITOBA FINAL EXAM

PAGE: 14 of 14

TIME: 3 hours

EXAMINER: Borgersen

SCRAP PAPER