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

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

 Search: Search body:
Forums (0)