advertisement

CS2022/ MA 2201 Homework #4 Solutions #1. (12 Points) Review a) Show that A U (BC) = (A U B )(A U C) STEP 1: A U (BC) (A U B )(A U C) Suppose x A U (BC). Then there are 2 cases: Case 1 x A Then x A U B and x A U C So x (A U B )(A U C) Case 2 x B C Then x B and Then x C Thus, x A U B and x A U C So x (A U B )(A U C) STEP 2: (A U B )(A U C) A U (BC) Suppose x(A U B )(A U C) Then xA or B and xA or C Again consider 2 cases: xA or x A Case 1 x A Then x A U (BC) Case 2 x A Then xB and C I.e., x B C So x A U (BC) b) Part a using Using Venn diagrams A U (BC) AUB AUC (A U B )(A U C) c) Show that: f(A B) f(A) Like above I will start with x f(A B) and show x f(A) Suppose x f(A B). Then a A B such that f(a) = x. Since a A B, it is the case that a A Since a A, f(a) f(A). But f(a) =x so x f(A) d) Using induction, show 2n < (n +1)! Basis n = 2: 2n = 22 = 4 (n +1)! = (2 + 1)! = 3! = 6 So 22 < (2 +1)! Induction Hypothesis 2n < (n +1)! n > 2 Induction Step: We need to show 2n+1< ((n +1) +1)! = (n + 2)! 2n+1 = 2* 2n < 2 * (n + 1)! <(n + 2) (n+1)! = (n+2)! n>2 Arithmetic Induction Hypothesis for n > 1 Arithmetic Def’n of factorial #2. Probability (Section 5.1) #20 What is the probability that a five-card poker hand contains a royal flush, that is, the 10, jack, queen, king and ace of one suit? There are only 4 royal flushes: 1 for each suit. P(royal flush) = 4/C(52,5) = 4/2598960 = .0000015 #3. Probability (Section 5.1) #28 To play the Pennsylvania superlottery, a player selects 7 numbers out of the first 80 positive integers. What is the probability that a person wins the grand prize by picking 7 numbers that are among the 11 numbers selected by the Pennsylvania lottery commission? We need to figure out the number of ways to choose the 11 numbers and in particular how to select the 11 numbers so as to contain the 7 numbers we want. For those 7 numbers, there will be 4 more (to make up 11) from the 80, so 80 – 7 other choices. Thus, there are C(73,4) ways to do this. Therefore the P(selected 7 numbers) = C(73,4)/C(80,11) = 3/28879240 = .0000001 ANOTHER WAY: C(11,7)/C(80,7) (7 of the possible 11 / number of ways to pick 7 numbers from 80) #4. Relations (Section 7.1): Let A = {1,2} and B = {1, 2, 3} and define binary relation R as: (x,y) R x – y is even a) State which ordered pairs of A x B are in R {(1,1), (1.3), (2,2)} b) Is 1 R 3?, yes because 2 | (1-3) 2 R 3?, no because 2 doesn’t | (2-3) 2 R 2? Give reasons yes because 2 | (2-2) #5. Relations (Section 7.3) Represent the relation of #4 a) using a Zero-One Matrix 1 1 0 1 2 2 0 1 3 1 0 b) using a graph #6. Relations (Section 7.1, 7.4) a) Show whether the relation below is reflexive, symmetric or transitive. If not, find the reflexive-closure, symmetric-closure and transitive-closure R = {(0,1), (0,2), (1,1), (1,3), (2,2), (3,0)} Not reflexive because (0,0) and (3,3) R Not symmetric because (0,1) R, but (1,0) R Not transitive because (1,3) and (3,0) R, but (1,0) R reflexive-closure (R) = R U {(0,0), (3,3)} symmetric-closure (R) = R U {(1,0), (2,0), (3,1), (0,3)} transitive-closure (R) = R U {(0,3), (1,0), (3,1), (3,2)} Pass 1 U {(1,2) (0,0), (3,3)} Pass 2 #7. Relations (Section 7.5) Let R be the relation of congruence modulo 3 on the set Z of integers. That is, for all m, n: m R n 3 | (m – n) Describe the distinct equivalence classes of R. [0] = {…, -6, -3, 0,3,6,…} [1] = {…,-2, 1,4,7, …} [2] = {…, -1, 2,5,8,… } #8. Relations (Section 7.5) #2 a,d Which of the following is an equivalence relation? State why or why not a) {(a,b) | a and b are the same age} reflexive: yes. Someone is the same age as themselves symmetric: yes. If x is the same age as y, then y is the same age as x transitive: yes. If x is the same age as y and y is the same age as z, then x is the same age as z b) {(a,b) | a and b have met No. If x has met y and y has met z, it is not necessarily true that x has met z