Math 220 Discrete Mathematics Final Exam

Math 220: Discrete Mathematics Final Exam Attempt all problems. Show all of your work. No notes, textbooks, calculators, or outside help may be used on this exam. 1. (5 points) Draw a truth table to show that the statement P ∨(Q∧ ∼ P ). is equivalent to the statement P ∨ Q. 2. (5 points) Give the negation of the following statement P : ∀r ∈ R, (r > 0 ⇒ (∃n ∈ N such that 1/n < r)). 3. (5 points) Prove that 1 · 1! + 2 · 2! + · · · + n · n! = (n + 1)! − 1 for all natural numbers n. 4. (5 points) Show that 6|(7n − 1) for all n ∈ N. 5. (10 points) Show that the product of a nonzero rational number and an irrational number is irrational. 6. (10 points) Define a function f : R → R by:  x − 2 f (x) = x − 4  1 if x 6= 4 . if x = 4 Show that f is a bijection. 7. (10 points) Let S be the power set of {1, 2, 3} (a) Determine which one of the following two relations is not an equivalence relation. (You only need to explain why your selection is not an equivalence relation. You are not required to explain why the other one is an equivalence relation.) i. AR1 B iff A ∩ B 6= ∅. ii. AR2 B iff |A| = |B|. (b) For the relation above that is an equivalence relation, find the associated partition of S into equivalence classes. 1 8. (10 points) Let A = R × R and let R be the relation on A given by (a, b)R(c, d) iff either a < c or else we have both a = c and b ≤ d. (a) Show that R is a partial order. (b) Determine whether or not R is a total order. 9. (10 points) The graph below represents a group of computers in a dorm, and the distance between them. We would like to network them, using the least amount of wire possible. A 2 14 E 5 10 8 10 I B 11 17 F 3 11 20 C G 15 12 10 J 9 K D H 18 6 L Use Kruskal’s Algorithm to find a minimal spanning tree on the graph shown above. (Please clearly highlight which edges you use and circle the numbers on those edges.) Find the amount of wire used in the resulting network. 10. (10 points) Find an Eulerian circuit on the graph below, indicating your path by drawing arrows and numbering the edges in the order that you traverse them. A D B E C F G H Write down the row corresponding to the vertex E in the adjacency matrix for the graph above. (Please order the vertices in alphabetical order.) 2 11. (20 points) For the following probability questions, you only need to set up the correct expression. You do not need to simplify your answers. (a) A committee of 7 is to be chosen from a group of 5 Republicans, 6 Democrats, and 4 Independents. Find the probability that at least one person from each political affiliation is included. (b) Find the probability that a random arrangement of the letters of ABRACADABRA begins with ABCD. (c) Two fair dice are rolled and your score is determined by the number facing up which is the greater of the two. Thus if you roll a 3 and a 2, your score is 3, and if you roll a pair of 3s your score is still 3. Find the probability that your score is odd. (d) 5 cards are dealt from a standard 52 deck of cards. (Recall that this deck can be divided into 4 suits (♥, ♦, ♣, ♠) and into 13 ranks (2−10, J, Q, K, A).) Find the probability that it contains 4 of a kind (i.e. 4 cards of the same rank). (e) Three kids find a cluster of 15 quarters that have fallen on the ground and each attempts to pick up as many as they can (rushing to grab them before the others do). Find the probability that each child gets at least 2 quarters. 3