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

Home > Logic
Mutually friendly 3 (Posted on 2012-08-05) Difficulty: 4 of 5
Prove that if any two people are either friends or strangers, then any group of 18 people contains either 4 mutual friends or 4 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.)
Some Thoughts 5 mutual friends or 5 mutual strangers | Comment 9 of 11 |
What is the minimum number of people required to guarantee that a group contains either 5 mutual friends or 5 mutual strangers?  This is apparently a VERY difficult problem.  It is the Ramsay number designated as R(5,5).  I was interested to read in Wikipedia that:

"The exact value of R(5,5) is unknown, although it is known to lie between 43 (Geoffrey Exoo) and 49 (McKay and Radziszowski) (inclusive).  Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens."

Maybe I should have called it a VERY VERY difficult problem.

Edited on August 7, 2012, 1:01 pm
  Posted by Steve Herman on 2012-08-07 12:59:13

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 (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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