Problem
COM-B1-M09-P024 Six People
Prove that among any \(6\) people, there are either \(3\) mutual acquaintances or \(3\) mutual strangers.
Choose one person and split the others into those acquainted and not acquainted with that person.
Choose a person \(A\). Among the other \(5\) people, by the pigeonhole principle there are either \(3\) who know \(A\), or \(3\) who do not know \(A\). First suppose \(A\) knows \(B,C,D\). If among \(B,C,D\) there is an acquaintance pair, say \(B\) and \(C\), then \(A,B,C\) are three mutual acquaintances. If there is no acquaintance pair among \(B,C,D\), then \(B,C,D\) are three mutual strangers. The second case, with three people not acquainted with \(A\), is analogous: if among them there is a non-acquaintance pair, it together with \(A\) gives three mutual strangers; if not, those three are mutual acquaintances.
Strong for Book 1: first step toward Ramsey theory.