Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share
    
Are you attempting to prove an analogue of this theorem? If so, I think the problem needs to be stated with an 'or'; for instance, nothing is stopping you from coloring each edge blue. –  user17794 Jun 14 '12 at 20:54
    
Actually, you're right. It is an OR! i've edited the question again. –  Shokodemon Jun 14 '12 at 21:26
    
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. –  Erick Wong Jun 14 '12 at 22:52

2 Answers 2

up vote 2 down vote accepted

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

share

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.

share
1  
I went ahead and assumed that you meant to put 'or'...instead of orange. ;) –  Cameron Buie Jun 14 '12 at 21:26

This site is currently not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .