In
Mutually friendly, we proved that if any two people are either friends or strangers, then any group of six people either contains 3 mutual friends or 3 mutual strangers, or both. Now, they can also be enemies.
Suppose that any two people are either friends, enemies, or strangers. Prove that any group of 17 people either contains 3 mutual friends, 3 mutual enemies, or 3 mutual strangers.
Assume that you plus 16 others are in the group of 17. Divide the remaining 16 into three groups, based on your relationship with them. One of the groups must have at least 6 people. Without loss of generality, assume that the largest group contains people all of whom are your enemies. If any two of them are enemies of each other, then those two and you form a group of three enemies, and we are done. Otherwise, that group of at least 6 people who are enemies to you are all either friends or strangers to each other. It has been previously proven in Mutually friendly, that if a group of 6 are all friends or strangers, then the group must contain at least 3 mutual friends or 3 mutual strangers, or both.
So, any group of 17 people must contain at least 3 mutual friends, 3 mutual enemies, or 3 mutual strangers.
Is 17 the smallest number necessary to guarantee this? I don't know, but it certainly seems possible.
Proof (spoiler)
