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 randon student A and let B a student in the lsit of A

A has 168 students in his list so 168 students has A in their list . [becuase of codition:if student A puts student B on their list, then student B will also have student A on their list ]

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

168 stduents 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 stduents has C in their list .and there should be atleast 2 studenst from S in this 168 because there are only 166 students other than students from S

so there is atleast one student who wansts 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.