MFC-UNIT-2-5.Inclusion-Exclusion

 

	Inclusion-Exclusion
1.	Which one of the following problem types does inclusion-exclusion principle belong to? a) Numerical problems b) Graph problems c) String processing problems d) Combinatorial problems Answer: d Explanation: Inclusion-Exclusion principle is a kind of combinatorial problem. It is a counting technique to obtain the number of elements present in sets( two, three , etc.,).	D
2.	Which of the following is a correct representation of inclusion exclusion principle (|A,B| represents intersection of sets A,B)? a) |A U B|=|A|+|B|-|A,B| b) |A,B|=|A|+|B|-|A U B| c) |A U B|=|A|+|B|+|A,B| d) |A,B|=|A|+|B|+|A U B| Answer: a Explanation: The formula for computing the union of two sets according to inclusion-exclusion principle is |A U B|=|A|+|B|-|A,B| where |A,B| represents the intersection of the sets A and B.	A
3.	____________ is one of the most useful principles of enumeration in combinationatorics and discrete probability. a) Inclusion-exclusion principle b) Quick search algorithm c) Euclid’s algorithm d) Set theory Answer: a Explanation: Inclusion-exclusion principle serves as one of the most useful principles of enumeration in combinationatorics and discrete probability because it provides simple formula for generalizing results.	A
4.	Which of the following is not an application of inclusion-exclusion principle? a) Counting intersections b) Graph coloring c) Matching of bipartite graphs d) Maximum flow problem Answer: d Explanation: Counting intersections, Graph coloring and Matching of bipartite graphs are all examples of inclusion-exclusion principle whereas maximum flow problem is solved using Ford-Fulkerson algorithm.	D
5.	Who invented the concept of inclusion-exclusion principle? a) Abraham de Moivre b) Daniel Silva c) J.J. Sylvester d) Sieve Answer: a Explanation: The concept of inclusion- exclusion principle was initially invented by Abraham de Moivre in 1718 but it was published first by Daniel Silva in his paper in 1854.	A
6.	According to inclusion-exclusion principle, a n-tuple wise intersection is included if n is even. a) True b) False Answer: b Explanation: According to inclusion-exclusion principle, a n-tuple wise intersection is included if n is odd and excluded if n is even.	B
7.	With reference to the given Venn diagram, what is the formula for computing |AUBUC| (where |x, y| represents intersection of sets x and y)? a) |A U B U C|=|A|+|B|+|C|-|A,B|-|A,C|-|B,C|+|A, B,C| b) |A, B,C|=|A|+|B|+|C|-|A U B|-|A U C|-|B U C|+|A U B U C| c) |A, B,C|=|A|+|B|+|C|+|A,B|-|A,C|+|B,C|+|A U B U C| d) |A U B U C|=|A|+|B|+|C| + |A,B| + |A,C| + |B,C|+|A, B,C| Answer: a Explanation: The formula for computing the union of three sets using inclusion-exclusion principle is|A U B U C|=|A|+|B|+|C|-|A,B|-|A,C|-|B,C|+|A, B,C| where |A,B|, |B,C|, |A,C|, |A,B,C| represents the intersection of the sets A and B, B and C, A and C, A, B and C respectively.	A
8.	Which of the following statement is incorrect with respect to generalizing the solution using the inclusion-exclusion principle? a) including cardinalities of sets b) excluding cardinalities of pairwise intersections c) excluding cardinalities of triple-wise intersections d) excluding cardinalities of quadraple-wise intersections Answer: c Explanation: According to inclusion-exclusion principle, an intersection is included if the intersecting elements are odd and excluded, if the intersecting elements are even. Hence triple-wise intersections should be included.	C
9.	Counting intersections can be done using the inclusion-exclusion principle only if it is combined with De Morgan’s laws of complementing. a) true b) false Answer: a Explanation: The application of counting intersections can be fulfiled if and only if it is combined with De Morgan laws to count the cardinality of intersection of sets.	A
10.	Using the inclusion-exclusion principle, find the number of integers from a set of 1-100 that are not divisible by 2, 3 and 5. a) 22 b) 25 c) 26 d) 33 Answer: c Explanation: Consider sample space S={1,…100}. Consider three subsets A, B, C that have elements that are divisible by 2, 3, 5 respectively. Find integers that are divisible by A and B, B and C, A and C. Then find the integers that are divisible by A, B, C. Applying the inclusion-exclusion principle, 100 − (50 + 33 + 20) + (16 + 10 + 6) − 3 = 26.	C