y +1/1/60+ y
MATH-UA 120.006 Discrete Mathematics
PRACTICE FINAL EXAMINATION
Spring 2019
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
Code the eight digits of your N number to the left, and
write your name below.
Name:
READ THE FOLLOWING INFORMATION.
• You have until the end of class to finish this exam.
• Fixed-response questions on this exam will be graded by computer. Please fill in the bubbles completely
and use pencil in case you want to change your responses.
NO YES NO
Too light No crossouts
Please do not write over the four dots at the corners of the pages, or the code at the top of each page.
• Calculators, books, notes, and other aids are not allowed.
• You may use the backs of the pages or the extra pages for scratch work. Do not unstaple or remove pages
as they can be lost in the grading process. Do not use other paper for scratch work.
• Please do not put your name on any page besides this page.
! DO NOT BEGIN THIS EXAM UNTIL SIGNALED TO DO SO. !
For office use only Check out: Check in: Finished:
y y
y +1/2/59+ y
(This page intentionally left blank.
You can use it for scratch work. Please do not remove it.)
y y
y +1/3/58+ y
In each of the multiple choice items below, select the best answer.
Question 1 Which of these is a counterexample to the statement, “If n! = n, then n = 0 or n = 1?”
A 1
B 3
C 2
D 0
E −1
Question 2 Which of these is the negation of the statement, “All the young dudes carry the news”?
A All the young dudes do not carry the news.
B Some of the young dudes carry the news.
C Only one of the young dudes carries the news.
D Some of the young dudes do not carry the news.
E All the young dudes carry the shoes.
Question 3 If A = {2,4,6} and B = {3,6,9}, which of these sets is A△B?
A {2,4}
B {2,3,4,9}
C {2,3,4,6,9}
D {6}
E {3,9}
Question 4 The five sides of a pentagon are to be colored, each with one of three differently colored pens.
All five sides must not be the same color. Two colorings of the pentagon are the same if one can be rotated into
the other. How many different colorings of the pentagon are possible?
A
35 −3
5!
B
35
5!
C 35 −3
D 35
E
35 −3
5
Question 5 Let σ be the element of S7 whose cycle representation is (1,4,2)(3,6)(5)(7). Which is the
smallest number k for which σ k = ι?
A 6
B 12
C 2
D 3
E 5
y y
y +1/4/57+ y
Question 6 Which of these is −17div5?
A −3
B −4
C 4
D 3
E −2
Question 7 Which of these is equal to gcd(119,175)?
A 119
B 17
C 1
D 7
E 25
Question 8 Suppose that G is a graph whose components are G1 and G2. Suppose that ω(G1) = 3 and
ω(G2) = 4. Which of these is ω(G)?
A 7
B 3
C 1
D 4
E 6
Question 9 How many cut vertices does the graph below have?
A 2
B 4
C 5
D 1
E 3
Question 10 Which of the graphs below is a tree?
A V = {1,2,3}, E = {{1,2}}
B V = {1,2,3}, E = {{1,3} ,{1,2}}
C V = {1,2,3}, E =∅
D V = {1,2,3}, E = {{1,3}}
E V = {1,2,3}, E = {{1,2} ,{1,3} ,{2,3}}
y y
y +1/5/56+ y
Questions with a ♣ by them indicate more than one option may be correct. You must select all correct options
and none of the incorrect options to earn full credit.
Question 11 ♣ Which of the following graphs are connected?
A E1
B P6
C K5
D E2
E E3
Question 12 ♣ Which of these functions are injective?
A {(1,2),(2,3),(3,4),(4,1)}
B {(1,3),(2,3),(3,2),(4,3)}
C {(1,3),(2,2),(3,2),(4,4)}
D {(1,1),(2,2),(3,3)}
E {(1,1),(2,1),(3,1)}
Question 13 ♣ Which of the following relations are antisymmetric?
A < on Z B ≤ on Z C is-connected-to on the vertices of a simple graph D divides on Z E ⊆ on 2Z Question 14 ♣ Which of these is an invertible element of Z12? A 6 B 10 C 13 D 5 E 8 y y y +1/6/55+ y y y y +1/7/54+ y In each of the next four problems, indicate if the statement is true or false. Then give a short justification or counterexample. Question 15 If f : A → B and g : B → C are surjective functions. then g ◦ f : A → C is surjective. 0 1 2 3 Question 16 If D = {x ∈ Z : x | 24}, then |2D|= 256. 0 1 2 3 Question 17 If a is even and b is odd, then a2 +b2 is a not a multiple of 4. 0 1 2 3 Question 18 There are infinitely many surjective functions from Z to 2Z. 0 1 2 3 y y y +1/8/53+ y y y y +1/9/52+ y The remaining questions are free response questions. • Read and follow the instructions of every problem. • Show all of your work for purposes of partial credit. Full credit may not be given for an answer alone. • Justify your answers. Full sentences are not necessary but English words help. When in doubt, do as much as you think is necessary to demonstrate that you understand the problem, keeping in mind that your grader will be necessarily skeptical. Question 19 A lottery game involves matching exactly a set of 5 distinct numbers from the integers 155 (each ticket is one choice of five distinct numbers). How many tickets must you purchase to be guarantee matching all the numbers? 0 1 2 3 4 Question 20 Assuming the machine picks your numbers for you (at random), how many must you purchase to guarantee two tickets share a number? 0 1 2 3 4 y y y +1/10/51+ y (This page intentionally left blank. You can use it for scratch work. Please do not remove it.) y y y +1/11/50+ y Question 21 Let G be the graph below. Exhibit an Eulerian trail or tour, or show that none exists. 9 8 7 6 5 4 3 2 1 0 1 2 3 4 5 Question 22 (Unrelated to the problem above) Use Boolean algebra to simply the expression. ((p → q)∧ (¬r →¬q))→ (p → r) 0 1 2 3 4 5 y y y +1/12/49+ y (This page intentionally left blank. You can use it for scratch work. Please do not remove it.) y y y +1/13/48+ y Question 23 Let f : Z15 → Z15 be the function f (x) = 7⊗ x. Show that f is a permutation of Z15, and find f−1. 0 1 2 3 4 5 Question 24 With f as in the previous question, write f is a product of disjoint cycles. 0 1 2 3 4 5 y y y +1/14/47+ y (This page intentionally left blank. You can use it for scratch work. Please do not remove it.) y y y +1/15/46+ y Question 25 A graph is called bipartite if there exists a partition V (G) = X ∪Y such that every edge of G joins a vertex in X to a vertex in Y . Use induction to prove that trees with at least two vertices are bipartite. 0 1 2 3 4 5 6 7 8 9 10 y y y +1/16/45+ y (This page intentionally left blank. You can use it for scratch work. Please do not remove it.) y y