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.
Best Answer
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.