All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Mutually friendly (Posted on 2002-07-01)
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.)

 See The Solution Submitted by levik Rating: 3.0000 (5 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 No Subject | Comment 1 of 11
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

 Search: Search body:
Forums (1)