Assume that a club of students is organised into committees in such a way that e

Question

Assume that a club of students is organised into committees in such a way that each of the following statements (axioms) is true.

(a) There are at least two students in the club.

(b) Every committee is a collection of one or more students.

(c) For each pair of students there is exactly one committee on which both serve.

(d) No single committee is composed of all the students in the club.

(e) Given any committee and any student not on that committee, there exists exactly one committee on which that student serves which has no students of the first committee in its membership.

Based on the above axioms, prove that every student serves on at least two committees

Explanation / Answer

To prove every student serves on atleast two committees. We prove that no student serves on only in 1 committee or 0 committees.

First consider that there is a student S(say), who serves in one and only committee say C. From axiom 1 we have there are atleast 2 students in the club, there are other students who will be in other committees. All the remaining students cant be in committee C because axiom d) prohibits that fact, so they have to be distributed among other committee's. Lets say there is a committee B, where S doesnot belong (by assumption), form axiom e) we can say that none of students from B can be present in committee C.

from axiom c) We have for each pair of students we have one and only one committee where these two students work together. Now choose a student T from B and S from C, from axiom e, T does not belong to C and from c) there has to be a committee where T and S must work together, since it cant be C or B, lets say its D, where T and S works. Giving S works at both C and D, contradiction.

Now assume there is a student S who works on No committee. from first axiom it is evident that there are other students, so either they can work in other committee or they can be jobless like S, in either case from axiom c) we have for each pair of students there is a commom committee where they work together, so we are back to a contradiction that S working on a committee. Hence proved.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.