COMP 1805 Discrete Structures IAssignment 5Date Due: April 10, 2013Time Due: Before 2pm in the Boxes in Herzberg Room 3115Write down your name and student number oneverypage. The questions should be answered in order andyour assignment sheets must be stapled. Your assignment will not be graded if you do not follow these instructions.Unless otherwise stated, you must provide a proof or at the very least an explanation for each of your answers.Simply stating an answer is not sufficient.1. Consider a relationRdefined on the setA={-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7}. Determine forthe following if the relations are reflexive, symmetric, anti-symmetric, transitive, partial orders, equivalencerelations.(a)R={(a, b)|a=b}, if this is a partial order, draw the Hasse diagram.(b)R={(a, b)|a3=b3}, if this is a partial order, draw the Hasse diagram.(c)R={(a, b)|ab=0}, if this is a partial order, draw the Hasse diagram.(d)R={(a, b)|a > b2}, if this is a partial order, draw the Hasse diagram.2. LetAbe the set of all bit strings of length 12. LetRbe the relation define onAwhere two bit strings arerelated if the first 2 bits, the 4th bit and the 7th bit are the same. Show thatRis an equivalence relation andenumerate one bit string from each of the different equivalence classes ofR.3. Consider the Hasse diagram in Figure 1. Answer the following questions on the partial order represented bythe diagram.abcdefghijklmnoprstuFigure 1: Hasse Diagram(a) Find the maximal elements.(b) Find the minimal elements.1
COMP 1805ASSIGNMENT52(c) Is there a greatest element?(d) Is there a least element?(e) Find all upper bounds of{m, k, t}(f) Find all lower bounds of{c, d, t}(g) Find the greatest lower bound of{u, k, m}if it exists(h) Find the least upper bound of{b, f}if it exists.(i) Find the greatest lower bound of{p, k}if it exists4. Consider the Hasse diagram in Figure 1. Use topological sort to compute a valid linear order of the elements.5. How many bit strings of length 17 contain(a) at least 5 ones?(b) exactly 3 ones?(c) at most 7 zeros?6. How many 9 letter strings are there that contain at least 3 vowels (a vowel is one of{a,e,i,o,u})?7. How many bit strings of length 15 contain 9 consecutive 1’s or 9 consecutive 0’s?8. How many bit strings are there of length at least 8 and at most 14?9. Let A be the set{m, n, o, p, e, d, a, c, b,1,2,3,4,5}. Answer the following:(a) How many different relations can be defined on the setA?(b) How many different relationsTare there on A where(m, n)?Tand(3,4)?Tand(a, c)?T?(c) How many different symmetric relations are there?10. LetA={2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32}. Prove or disprove that if I select 10 distinct ele-ments from the setA, that there are at least two pairs of elements whose sum will be exactly 34.11. In poker, a flush is a 5-card hand where all the cards have the same suit. Recall that a deck of cards has 52cards. There are 4 suits (hearts, clubs, diamonds and spades) and each suit has 13 cards. How many differentflush hands can you have that consist only of hearts, diamonds or spades?12. Consider the following setS={x?Z|1=x=10010}. How many elements are there inSwhose digits addup to 9. For example 8001 is an element ofSwhose digits add up to 9.13. How many permutations of the letters A,B,C,D,E,F,G,H contain(a) the string BG?(b) the string ACD and GFH?(c) the string AC, BD, and GE?14. Suppose a group has 11 men and 9 women.(a) How many different 7 person teams can be made?(b) How many different 8 person teams can be made that contain at least 2 women?(c) How many different 9 person teams can be made that contain at least 2 women and at least 2 men?(d) How many different 6 person teams can be made that contain exactly 4 women?