Take any person X. They are either friends with at least 9 people or strangers with at least 9 people. Suppose X is friends with at least 9 people. Let S be a set of 9 of these people.

Take any person A in S. If A has less than 3 friends in S, then there are at least 6 people in S that are strangers with A. By Mutually friendly, these 6 people contain either 3 mutual friends or 3 mutual strangers. If they contain 3 mutual friends, then these 3 and X are 4 mutual friends. If they contain 3 mutual strangers, then these 3 and A are 4 mutual strangers. If A has at least 4 friends in S, then there are 4 people that are friends with both X and A. If any two of these people are friends, then these two, X, and A are 4 mutual friends. If they are all strangers, then they are 4 mutual strangers. Therefore, to avoid 4 mutual friends or 4 mutual strangers, A has to have exactly 3 friends in S.

There are 9 people in S, and each person has 3 friends in S. Therefore, there are 27 friendships in S. However, friendships are symmetric, so there must be an even number of friendships. That is a contradiction, so if X is friends with at least 9 people, then there are either 4 mutual friends or 4 mutual strangers.

A similar argument works if X is strangers with at least 9 people. Therefore, any group of 18 people contains either 4 mutual friends or 4 mutual strangers.

Comments: (
You must be logged in to post comments.)