Discrete math #2 - Questions and Answers

Question 1 List the first five common multiples in ascending order for each pair of numbers. a. 6 , 16 6,16 Answer: Step 1 Factors of 6: 6 = 1 × 2 × 3 6=1×2×3 Factors of 16: 16 = 1 × 2 × 2 × 2 16=1×2×2×2 Hence, common factors are multiples of 1 and 2. Step 2 Common multiples of 6 and 16 are: 48 , 96 , 144 , 192 , 240 48,96,144,192,240 Question 2 A 5-card hand is dealt from a perfectly shuffled deck. Define the events: A: the hand is a four of a kind (all four cards of one rank plus a fifth card), B: at least one of the cards in the hand is an ace. Are the events A and B independent? Answer: The four-of-a-kind hand has the pattern 𝐴 𝐴 𝐴 𝐴 𝐵 AAAAB where 𝐴 A and 𝐵 B are from distinct kinds. The number of such hands: 13 ( 1 1 ) × 4 ( 4 4 ) × 12 ( 1 1 ) × 4 ( 1 1 ) = 624 13( 1 1 ​ )×4( 4 4 ​ )×12( 1 1 ​ )×4( 1 1 ​ )=624 Total number of combinations of different hands: ( 52 5 ) = 2598960 ( 5 52 ​ )=2598960 𝑃 ( 𝐴 ) = Number of favorable outcomes Total number of hands = 624 2598960 = 0.00024 P(A)= Total number of hands Number of favorable outcomes ​ = 2598960 624 ​ =0.00024 Probability 𝑃 ( None of the card is Ace ) P(None of the card is Ace): 𝑃 ( None of the card is Ace ) = Hands with no Ace Total number of hands = ( 48 5 ) ( 52 5 ) = 0.6588 P(None of the card is Ace)= Total number of hands Hands with no Ace ​ = ( 5 52 ​ ) ( 5 48 ​ ) ​ =0.6588 𝑃 ( At least one of the cards is Ace ) = 1 − 𝑃 ( Hands with no Ace ) = 1 − 0.6588 = 0.3412 P(At least one of the cards is Ace)=1−P(Hands with no Ace)=1−0.6588=0.3412 Event 𝑃 ( 𝐴 ∩ 𝐵 ) P(A∩B): Number of hands with four of a kind and Ace: 1 × 4 ( 4 4 ) × 12 ( 1 1 ) × 4 = 48 + 48 = 96 1×4( 4 4 ​ )×12( 1 1 ​ )×4=48+48=96 𝑃 ( 𝐴 ∩ 𝐵 ) = 96 2598960 = 0.000037 P(A∩B)= 2598960 96 ​ =0.000037 Check independence: 𝑃 ( 𝐴 ) ⋅ 𝑃 ( 𝐵 ) ≠ 𝑃 ( 𝐴 ∩ 𝐵 ) P(A)⋅P(B)  =P(A∩B) 0.00024 ⋅ 0.3412 ≠ 0.000037 0.00024⋅0.3412  =0.000037 Thus, events A and B are not independent. Question 3 Consider a relation 𝑅 R on 𝑍 − { 0 } Z−{0} defined by the rule that ( 𝑥 , 𝑦 ) ∈ 𝑅 (x,y)∈R if and only if 𝑥 𝑦 > 0 xy>0. a) Prove that 𝑅 R is an equivalence relation. b) Determine all elements in the equivalence class containing 1. How many distinct equivalence classes are there? Answer: Given the relation 𝑅 R on 𝑍 − { 0 } Z−{0} defined by: ( 𝑥 , 𝑦 ) ∈ 𝑅  if and only if  𝑥 𝑦 > 0 (x,y)∈R if and only if xy>0 a) Prove 𝑅 R is an equivalence relation. Reflexive: For any 𝑥 ∈ 𝑍 − { 0 } x∈Z−{0}, 𝑥 2 > 0 x 2 >0. So ( 𝑥 , 𝑥 ) ∈ 𝑅 (x,x)∈R for all 𝑥 x. Hence, 𝑅 R is reflexive. Symmetric: If ( 𝑥 , 𝑦 ) ∈ 𝑅 (x,y)∈R, then 𝑥 𝑦 > 0 xy>0. Since 𝑥 𝑦 = 𝑦 𝑥 xy=yx, we have ( 𝑦 , 𝑥 ) ∈ 𝑅 (y,x)∈R. Hence, 𝑅 R is symmetric. Transitive: If ( 𝑥 , 𝑦 ) ∈ 𝑅 (x,y)∈R and ( 𝑦 , 𝑧 ) ∈ 𝑅 (y,z)∈R, then 𝑥 𝑦 > 0 xy>0 and 𝑦 𝑧 > 0 yz>0. Since 𝑦 ≠ 0 y  =0, multiplying gives 𝑥 ( 𝑦 𝑧 ) > 0 x(yz)>0, so ( 𝑥 , 𝑧 ) ∈ 𝑅 (x,z)∈R. Hence, 𝑅 R is transitive. Thus, 𝑅 R is an equivalence relation. b) Find the equivalence class of 1. [ 1 ] = { 𝑥 ∈ 𝑍 − { 0 }   ∣   1 ⋅ 𝑥 > 0 } = 𝑍 + [1]={x∈Z−{0} ∣ 1⋅x>0}=Z + Similarly: [ − 1 ] = { 𝑥 ∈ 𝑍 − { 0 }   ∣   − 1 ⋅ 𝑥 > 0 } = 𝑍 − [−1]={x∈Z−{0} ∣ −1⋅x>0}=Z − Thus, there are exactly 2 distinct equivalence classes: 𝑍 + Z + and 𝑍 − Z − . Question 4 Prove that discrete math the following statement (if true) or provide a counterexample (if false): For all 𝑛 ≥ 4 n≥4, 2 𝑛 − 1 2 n −1 is not a prime number. Answer: Counterexample: Let 𝑛 = 5 n=5, then: 2 𝑛 − 1 = 2 5 − 1 = 31 2 n −1=2 5 −1=31 31 is a prime number. Thus, the statement is false for 𝑛 = 5 n=5. Question 5 Express the following in set-builder notation: a) The set 𝐴 A of natural numbers divisible by 3. b) The set 𝐵 B of pairs ( 𝑎 , 𝑏 ) (a,b) of real numbers such that 𝑎 + 𝑏 a+b is an integer. c) The open interval 𝐶 = ( − 2 , 2 ) C=(−2,2). d) The set 𝐷 D of 20 element subsets of 𝑁 N. Answer: a) 𝐴 = { 𝑥 ∈ 𝑁   ∣   𝑥  is divisible by 3 } A={x∈N ∣ x is divisible by 3} b) 𝐵 = { ( 𝑎 , 𝑏 ) ∈ 𝑅 2   ∣   𝑎 + 𝑏 ∈ 𝑍 } B={(a,b)∈R 2  ∣ a+b∈Z} c) 𝐶 = { 𝑥 ∈ 𝑅   ∣   − 2 < 𝑥 < 2 } C={x∈R ∣ −2