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

Home > Logic
Mutually friendly (Posted on 2002-07-01) Difficulty: 2 of 5
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.)
Solution 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
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information