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.

A group of 6 people each pair is either a friend (acquaintance) or an enemy (stranger). It is to be proven that there are either 3 mutual friends or 3 mutual enemies in this group. I have an ad-hoc reasoning for this, but it is not yielding a big picture.

I would appreciate an approach or way of thinking about this which would make it easier to generalize it for n friends. i.e find the minimal number of mutual friends or enemies that can exist for a group of n people. My approach is getting cumbersome when I try for larger n.

(My reasoning) Any person either has (atleast 3 friends) OR (atleast 3 enemies). This is true because each person can be friend\enemy with five others and by the pigeonhole principle atleast one of the two holes (friend , enemy ) must contain 3 or more people. Consider one of the friends in the former case (or enemies in the latter). He has a relationship with the other two. There are three possibilities. FF, EE, EF. The first and last case results in 3 mutual friends. In the second case, we must consider the relationship between the remaining two. If they are friends, then there are three mutual friends. If they are enemies, then there are 3 mutual enemies.

share|improve this question
1  
This problem is part of Ramsey Theory; see also Wikipedia's page on the friends and strangers theorem –  Arturo Magidin Jun 1 '11 at 19:05

2 Answers 2

up vote 6 down vote accepted

That's a reasonable answer. I think my favorite way of viewing this question is to think of a complete graph on six vertices (i.e. each vertex is connected to each other vertex), where all edges are colored either red or blue. Then you are to show that there is either a red triangle or a blue triangle.

You could put your reasoning on this picture, as it becomes very easy to follow.

This is also a good time to first learn about Ramsey Theory - of which this is one of the easiest examples. Look here.

share|improve this answer
    
Ye Olde Ramsey Theory... This is the first problem Croot taught me about Graph&Ramsey Theory. –  Nicolas Villanueva Jun 1 '11 at 19:39

The trouble is that this problem gets quite more difficult as you increase $n$. This problem (called the party problem) was discussed by Paul Erd\H{o}s himself in this video.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.