Prove that any group of six people contains either 3 mutual friends or 3 mutual strangers.

(For the purpose of this problem any pair of people must be either friends or strangers.)

Take any person in the group. Call them Joe. They are either friends with at least 3 people or strangers with at least 3 people. Suppose they are friends with at least 3 people. If any two of the three are friends, then those two and Joe are 3 mutual friends. If they are all strangers, then they are 3 mutual strangers. Either way, there is a group of mutual friends or strangers. A similar argument proves that if the first person is strangers with at least 3 people, then there is a group of mutual friends or strangers.

Posted by Math Man on 2011-04-25 20:08:22