If I choose any four students among a class, at least one of the four knows all of the other three. Prove that there must be a student who knows everybody in the class.
Asked
Active
Viewed 155 times
-1
-
What are your own thoughts? Is the relation "$a\text{ knows }b$" symmetric? – Arthur Oct 27 '14 at 12:14
-
1Technically, if there are $3$ students in the class, it may not be the case. – Traklon Oct 27 '14 at 12:15
-
yes- the relation is symmetric. I think that A can either not know 0 1 or 2 students. So we break into cases. When A knows no one it is clear. When A knows 1 student we can make a group with A, the 1 student, and 2 random students. But from here I'm not sure how to prove someone knows everyone. – jack johnson Oct 27 '14 at 12:16
-
2This question has been deleted by the OP. – Clement C. Oct 27 '14 at 12:38
-
Possible Duplicate http://math.stackexchange.com/questions/990537/proving-that-if-one-person-in-any-group-of-four-knows-three-then-someone-knows – Oct 27 '14 at 13:59
1 Answers
3
You have to assume that there are at least $4$ students in the class, and that the relation of knowing is symmetric. I will prove the contrapositive: if there is no student who knows everybody in the class, then there is a group of four in which none of them knows the other three.
Choose a student A. Choose another student B who does not know A. Now there are two cases.
Case 1. There is a third student who knows A and B. Let C be such a student, and choose another student D who does not know C.
Case 2. There is no student who knows both A and B. Choose two more students C and D.
More generally, if there are $n$ students in the class and none of them knows all the other students in the class, then for each (positive) even integer $k\le n$ there is a set of $k$ students, none of whom know all the others.
In the language of graph theory: if $G$ is a graph of order $n$ with no isolated vertices, and if $0\lt2m\le n$, then $G$ has a subgraph of order $2m$ with no isolated vertices.
bof
- 78,265