In a class of at least four people, the following applies: if four of them sit down at a round table, there is always someone who knows both of their neighbors or does not know both of their neighbors. Prove that it is possible to divide the people into two groups (one of which may be empty) such that in one group everyone knows each other and in the other group no one knows each other.
(If person knows person , then also knows .)
Solution
Of all possible groups of people we can form in this class, we consider the groups in which everyone knows each other, and from these we take one with as many people as possible. (This largest group exists: there are finitely many people and there is at least a group of people who all know each other, namely a group consisting of one person.) Call this group . We prove that the group and the group consisting of the rest of the people satisfy the condition.
Since everyone in knows each other, we only need to prove that all people outside do not know each other. Suppose there are and outside who do know each other. Since is as large as possible, contains a person who is not an acquaintance of . Similarly, contains a person who is not an acquaintance of . We now first prove that we can choose and to be different from each other. If not, there is a unique person in who does not know and . For all other people in , it then holds that they know both and . Now consider the set . In this group of people, everyone knows each other: the people from know each other, and know each other, and everyone in knows both and . This group is, however, larger than , a contradiction.
Therefore, we may assume that and are different people. Note that and know each other, as they are both in . If now , and sit down at a round table in that order, everyone knows exactly one of their neighbors: and know each other and and know each other, but and do not know each other, and the same goes for and . This is a contradiction to the given condition. We conclude that the division into and the rest of the people satisfies the condition.