Our task is to prove that there exists 4 strangers OR 4 friends within this group of 9 guests.
Now what's the best way to go about finding this out?
Using the Friendship Theorem? or using the Pigeonhole Principle ?
Our task is to prove that there exists 4 strangers OR 4 friends within this group of 9 guests.
Now what's the best way to go about finding this out?
Using the Friendship Theorem? or using the Pigeonhole Principle ?
Here is a counterexample to the claim that nine guests is sufficient to force four mutual friends or four mutual strangers.
Suppose your guests are divided into three disjoint cliques (in both senses of the word). That is, the guests are divided into three groups such that
By this construction, there cannot be four individuals that all know each other, since at least two of them belong to different groups (and so are strangers). Similarly, there cannot be four individuals that are mutual strangers, since at least two of them belong to the same group (and so are friends).
I'll assume that by 'strangers' you mean pairwise mutual strangers, similarly for friends, and that the 'and' is replaced with an 'or' (otherwise the statement is trivially false.) In this case, the problem can be reduced to monochromatic embeddings of complete graphs, ala Ramsey Numbers. In this case, the numbers still lend themselves to a false statement. If one of the fours is replaced with a three, however, the statement is true.