it is know that among any group of 3 students in a class 2 of them are friends. the total number of students is 25. prove that there is a student who has at least 12 friends.
thnx
justanotherperson
Hi,
suppose every student has less than 12 friends. Pick any student A, he has less than or exactly 11 friends, so the number of students other than A who are not friends with A is greater or equal to 25-12 = 13, let student B be one of them. B has also less than or exactly 11 friends. Since 13-12=1>0, there must be at least one student C, other than A and B, who is not friends with A and is not friends with B. Since A and B are not friends with each other, A,B,C is a group of three students and no two of them are friends, which contradicts our assumption. Thus there must be a student who has at least 12 friends.