0
$\begingroup$

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 ?

  • 0
    The Friendship Theorem (the one about the friendship graph being the unique one with a certain adjacency property) seems to have nothing to do with this question.2012-06-14

2 Answers 2

2

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

  • everyone knows everyone else within their own group and
  • nobody knows anyone else outside their own group.

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).

0

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.

  • 1
    I went ahead and assumed that you meant to put 'or'...instead of orange. ;)2012-06-14