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

We start by looking for some combination of friends and strangers that allows for no triples, and show that such a combination can't be found.

Suppose person A (Call him Abe) knows persons B and C (Bill and Carl) In order not to form a triple, Bill and Carl must be strangers. If Abe also knows Dave, then Dave must be a stranger to both Bill and Carl, but then Bill, Carl, and Dave would form a triple of strangers. So Dave and Abe must be strangers. Likewise, Ed must be a stranger to Abe. But he must be a friend of Dave's, or together they would form a Triple of strangers with Abe.

Now Frank can't be a friend of Abe's for the same reason Dave and Ed couldn't. But by the same logic, he can't be a strnger either. Since he must be one or the other, it is impossible to avoid a triple.

Starting with any of the six, and adding the other five in any order, still leaves us at this point: adding the sixth forces a triple.

Posted by TomM on 2002-07-01 15:08:34