Facts about Friends and Strangers
Alex Y
This one seems not to be going anywhere.
It is interesting to me that the difficulty of solving it grows VERY fast as the size of the friend or stranger groups grows.
To make sure you have a friend or stranger group of 4, you need to have a party of 18 people.
For five (the very unfair version of this puzzle I first saw), the best mathematicians with modern computers can do is to say that the smallest party assuring you of a group of 5 friends or strangers is in the range of 43 to 48.
Why can't they just grind out the possibilities and see what works? That's where it gets interesting. To test all the possibilities with a parties of up to 48 it would take approximately 10^680 times as many calculations as the groups of 3 case.
If you are like me, it is hard to imagine what a number like that is. So I looked at some other large numbers for perspective. If every atom in the observable universe (10^80) were a computer able to solve the 3-group problem in 1 billionth of a second, those computers working since the big bang (13.9 billion years, or 4.3x10^17 seconds) would still be woefully inadequate to examine all the possibilities to determine which of 43-48 is the smallest number guaranteeing a group of 5!
CS pros here, please set me straight if I am misinterpreting the statement that complexity of this problem is O(2^(n^2)).
Mathematicians have used other methods than brute force to seek answers, but results quickly get pretty meaningless. For a group of ten friends or strangers, the best they have been able to say is that you need a party of somewhere between 798 and 23,556 guests!
I'll leave the 3-group problem out there for a while in case anyone is still working on it (and may be able to back into it based on info here).
