Problem

Source: OLCOMA Costa Rica National Olympiad, Final Round, 2015 C2 p3

Tags: combinatorics



In a set X of n people, some know each other and others do not, where the relationship to know is symmetric; that is, if A knows B. then B knows A. On the other hand, given any4 people: A,B,C and D: if A knows B, B knows C and C knows D, then it happens at least one of the following three: A knows C,B knows D or A knows D. Prove that X can be partition into two sets Y and Z so that all elements of Y know all those of Z or no element in Y knows any in Z.