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 Confirmed: 17 is the minimum Comment 4 of 4 |
I just looked this up.  This is a problem addressed by "Ramsey's theorem" (look it up in Wikipedia).  The Ramsey number R(3,3,3) does in fact equal 17.  So 16 people will not guarantee it.
  Posted by Steve Herman on 2011-07-02 22:18:46
Please log in:
Remember me:
Sign up! | Forgot password

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

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