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

Home > Logic
Mutually friendly 2 (Posted on 2011-07-01) Difficulty: 3 of 5
In Mutually friendly, we proved that if any two people are either friends or strangers, then any group of six people either contains 3 mutual friends or 3 mutual strangers, or both. Now, they can also be enemies.

Suppose that any two people are either friends, enemies, or strangers. Prove that any group of 17 people either contains 3 mutual friends, 3 mutual enemies, or 3 mutual strangers.

See The Solution Submitted by Math Man    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Proof (spoiler) | Comment 3 of 4 |
Assume that you plus 16 others are in the group of 17.  Divide the remaining 16 into three groups, based on your relationship with them.  One of the groups must have at least 6 people.  Without loss of generality, assume that the largest group contains people all of whom are your enemies.   If any two of them are enemies of each other, then those two and you form a group of three enemies, and we are done. Otherwise, that group of at least 6 people who are enemies to you are all either friends or strangers to each other. It has been previously proven in Mutually friendly, that if a group of 6 are all friends or strangers, then the group must contain at least 3 mutual friends or 3 mutual strangers, or both.  So, any group of 17 people must contain at least 3 mutual friends, 3 mutual enemies, or 3 mutual strangers. 

Is 17 the smallest number necessary to guarantee this?  I don't know, but it certainly seems possible.  

  Posted by Steve Herman on 2011-07-01 17:31:51
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


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

Chatterbox:
Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information