Your TAs are helping the students to form homework groups, so they have every st

Question

Your TAs are helping the students to form homework groups, so they have every student fill out a form listing all of the other students who they would be willing to work with. There are 251 students in the class, and every student lists exactly 168 other students who they would be willing to work with. For any two students in the class, if student A puts student B on their list, then student B will also have student A on their list. Show that there must be some group of 4 students who are all willing to work with one another.

Explanation / Answer

Let us take any random student A and let B a student within the list of A.

A has 168 students in his list thus 168 students incorporates a in their list. [Because of condition: if student A puts student B on their list, then student B will have student A on their list]

168 students has A in their list (167 other than B)

168 students has B in their list (167 other than A)

Since total no of other students are only 249 (251-1-1 i.e. A, B excluded)

There can be only 82(i.e. 249-167) students who have B in their list and not A

There should be 85 i.e. (167-82) students who have both A and B in their list

Let us take any student C from 85 students who have both A and B in their list

There are 84 students other than C who have both A and B in their list let us call this set of students as set S

168 students has C in their list .and there should be at least 2 students from S in this 168 because there are only 166 students other than students from S

So there is at least one student who wants C, A, B in his list

So there is one group of 4 who are all willing to work with one another.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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