Maths Olympiad Prep

Library / /464 of 520

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it

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 AA knows person BB, then BB also knows AA.)

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 XX. We prove that the group XX and the group consisting of the rest of the people satisfy the condition.
Since everyone in XX knows each other, we only need to prove that all people outside XX do not know each other. Suppose there are AA and BB outside XX who do know each other. Since XX is as large as possible, XX contains a person AA^{\prime} who is not an acquaintance of AA. Similarly, XX contains a person BB^{\prime} who is not an acquaintance of BB. We now first prove that we can choose AA^{\prime} and BB^{\prime} to be different from each other. If not, there is a unique person C=A=BC=A^{\prime}=B^{\prime} in XX who does not know AA and BB. For all other people in XX, it then holds that they know both AA and BB. Now consider the set (X\C){A,B}(X \backslash C) \cup\{A, B\}. In this group of people, everyone knows each other: the people from XX know each other, AA and BB know each other, and everyone in XX knows both AA and BB. This group is, however, larger than XX, a contradiction.
Therefore, we may assume that AA^{\prime} and BB^{\prime} are different people. Note that AA^{\prime} and BB^{\prime} know each other, as they are both in XX. If now A,B,BA, B, B^{\prime}, and AA^{\prime} sit down at a round table in that order, everyone knows exactly one of their neighbors: AA and BB know each other and AA^{\prime} and BB^{\prime} know each other, but AA and AA^{\prime} do not know each other, and the same goes for BB and BB^{\prime}. This is a contradiction to the given condition. We conclude that the division into XX and the rest of the people satisfies the condition.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.