Mutual friends solutions

See the original puzzle

This one was first solved by Secret Squïrrel.

There are six people in the group. Choose one person, named person A. Person A has a relationship with each of the five other people. Each relationship is one of two types, friend or stranger. If there are five relationships of two kinds, then there must exist at least three relationships which are of the same kind. (This is called the pigeonhole principle.)

So now we can say that person A has the same kind of relationship with persons B, C, and D. Suppose that this relationship is friendship. If the relationship between B and C is a friendship, then A, B, and C are a group of three mutual friends. Similarly, if the relationship between B and D is a friendship, or if the one between C and D is a friendship, then you will be able to find a group of three mutual friends. However, if none of these pairs (B-C, B-D, C-D) are friendships, then they must all be strangers. And so, B, C, and D must constitute a group of three mutual strangers.

If A is stranger to B, C, and D, then a similar proof holds. No matter what, there must exist either a group of three mutual friends or three mutual strangers.

There are seventeen people in a group. Choose one person, named person A. Person A has a relationship with sixteen other people. Each of those relationships is one of three types: friends, strangers, or rivals. Therefore (by the pigeonhole principle), there must exist six relationships which are of the same type. I will refer to this relationship as "rivals", but the same argument holds even if they are friends or strangers.

So now we have person A, who is rivals with persons B, C, D, E, F, and G. If any two people out of B, C, D, E, F, and G are rivals with one another, then together with person A, they form a group of three mutual rivals. However, if none of the relationships between B, C, D, E, F, and G are rivalries, then they must all be friends or strangers with one another. But, as we proved earlier, if there are six people who are only strangers or friends with one another, then there must exist a group of three people who are either mutual friends or mutual strangers.

So I hope my proof wasn't too hard to understand. You may also see Secret Squïrrel's wording of the proof.