In a class of 16 students, 16 committees C_1, C_2,..., and C_16 are formed using students...

Transcribed Image Text:

In a class of 16 students, 16 committees C_1, C_2,..., and C_16 are formed using students of the class. All 16 committees are distinct in that no two committees have identical sets of students. That is C_i C_j for all 1 #j. Show or disprove that there exists a students in the class such that C_iu{s} #C_ju{s} for all i #j. We explain this question with a smaller example. Consider a class with four students P, Q, R, and S. The four committees C_1=(P), C_2={Q}, C_3=(P, Q} and C_4=(P, Q.S) are distinct. Suppose we add P to the four committees. If P is on the committee already, then there is no change in the committee when P is added to it. After the addition of P, the resulting four committees are C_1U{P}={P),C_2U{P}-{Q.P}.C_3U{P}-{P.Q) and C_4U(P)-{P.Q.S). The resulting committees are not distinct as the committees C_2U(P)=C_3U{P}-{P, Q} have the same set of students. Similarly adding Q or S to the four committees will not result in four distinct committees. However, adding R to the four committees will result in four distinct committees. That is, C_1U{R}-{P.R}.C_2U{R}-{Q.R}.C_3U{R}-{P.Q.R} and C_4U{R}={P.Q.S.R} are all distinct. Can we always find such a student that makes all the resulting committees distinct? This is the gist of the question. Experiment with other sets of four committees to acquire a feel for the problem. In a class of 16 students, 16 committees C_1, C_2,..., and C_16 are formed using students of the class. All 16 committees are distinct in that no two committees have identical sets of students. That is C_i C_j for all 1 #j. Show or disprove that there exists a students in the class such that C_iu{s} #C_ju{s} for all i #j. We explain this question with a smaller example. Consider a class with four students P, Q, R, and S. The four committees C_1=(P), C_2={Q}, C_3=(P, Q} and C_4=(P, Q.S) are distinct. Suppose we add P to the four committees. If P is on the committee already, then there is no change in the committee when P is added to it. After the addition of P, the resulting four committees are C_1U{P}={P),C_2U{P}-{Q.P}.C_3U{P}-{P.Q) and C_4U(P)-{P.Q.S). The resulting committees are not distinct as the committees C_2U(P)=C_3U{P}-{P, Q} have the same set of students. Similarly adding Q or S to the four committees will not result in four distinct committees. However, adding R to the four committees will result in four distinct committees. That is, C_1U{R}-{P.R}.C_2U{R}-{Q.R}.C_3U{R}-{P.Q.R} and C_4U{R}={P.Q.S.R} are all distinct. Can we always find such a student that makes all the resulting committees distinct? This is the gist of the question. Experiment with other sets of four committees to acquire a feel for the problem.

Answer rating: 100% (QA)

To prove or disprove the statement lets consider a class with 16 students and 16 distinct committees ... View the full answer