advertisement

INDIAN INSTITUTE OF TECHNOLOGY, KHARAGPUR Date 22.09.2008 AN Time: 2 Hrs. Full Marks 25 No. of Students: 65 Autumn Semester:, 2008 Department: Computer Science and Engineering Sub. No: CS 21001 2nd Yr. B. Tech.(Hons.) Sub. Name: Discrete Structures Question 1 [10 x 1.5] a) Prove that if m and n are relatively prime and m.n is a perfect square, then m and n are each perfect squares. b) Show that if A and B are n n matrices and A1 , B 1 both exist, then AB c) Let 1 B 1 A1 . Tn be a sequence of positive integers defined recursively as: T0 2 Tn Tn21 Tn22 ... T12 T02 for all n 1 Prove the following assertions. You may use induction on n, whenever necessary i). Tn Tn1 Tn1 1 ii). Tn 22n iii). Tn 23n for all n N for all n 2 for all n N0 0 d) Prove that if the product of integers p and q is odd, then both p and q must be odd. e) Show that in any set X of people there are two members of X who have the same number of friends in X. (It is assumed that |X| is at least 2, and if x is a friend of x’ then x’ is a friend of x.) f) The set Y consists of the following numbers: Y = {1, 31/2, 3, 33/2, …, 319/2, 310}. In how many ways can a pair of distinct numbers be selected from the set Y so that their product is greater than or equal to 310? g) Find a recurrence relation for the number of bit strings of length n that have three consecutive 0s. Use this relation to find the number of such bit strings of length 7. h) Given that |A| = 24 and an equivalence relation q on A partitions it into three distinct equivalence classes A1, A2, and A3, where |A1| = |A2| = |A3|, what is |q|? Question II [2 + 2 + 1 +1] a) Let A = {1,2,3,4,5}, R and S are equivalence relations, R = {(1,1), (1,2), (2,1), (2,2), (3,3), (3,4), (4,3), (4,4), (5,5)}, and S = {(1,1),(2,2),(3,3),(4,4),(4,5),(5,4),(5,5)}. Find the smallest equivalence relation containing R and S and compute the partition of A it produces. b) (a) The figure defines two relations on the set {a,b,c,d}. Find the list and matrix representations of those relations. (b) A relation on the set {a,b,c,d} is defined by the following list: {(a,c), (c,c), (a,a), (b,b), (c,a), (d,b), (d,a)}. Draw its directed graph representation. c) What is wrong with the following “proof” that every symmetric and transitive relation is reflexive? If (a,b) R then (b,a) R by symmetry. By transitivity (a,a) R. Therefore R is reflexive. d) Backtrack to find an explicit formula for the sequence defined by the recurrence relation bn = 2.bn-1 = 1 with initial condition b1 = 7. Question III [2 + 2] Prove a) Let R be a relation on a set A. Then R∞ is the transitive closure of R. b) Let R be an equivalence relation on a set A and let a € A and b € A. Then a R b if and only if R(a) = R(b) .