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.)

(In reply to re: IQ Test by levik)

Actually I did not prove that a group of 5 people can avoid triples. all I proved was that a group of six cannot.

To prove that five can avoid triples I would need to examine four reationships that I never toched on in my previous analysis: Bill-Dave, Bill-Ed, Carl-Dave and Carl-Ed.

Bill cannot be a friend to both Dave and Ed, Neither can Carl. But Dave cannot be a stranger to both Bill and Carl. Neither can Ed

The following relatioships fulfill these conditions, and finally prove it is possible for five people to have no triples:

Bill and Dave are friends
Bill and Ed are strangers
Carl and Dave are strangers
Carl and Ed are friends.

Posted by TomM on 2002-07-02 08:01:25