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.
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
5 mutual friends or 5 mutual strangers
