StarGateWars Forums

"If you you host a party, what is the minimum number of guests to ensure that either there is a group of n people that know each other OR that there is a grouping of n people that do not know each other" For n=3 the answer is that you need 6 people and for n=4 the answer (I think!) is either 17 or 18 (I am in the process of checking this out with Dr D R Woodall in the School of Mathematics who is a combinatorics specialist).

The aim of the project is NOT to do advanced combinatorics for n>4 but to investigate the case n=3 in detail,using the Internet Movies Database and its pairwise co-starring relationships. Then to provide a visually appealing and informative interface to show co-starring relationships of groupings of movie actors in dinner parties of size M. The case M=5 is particularly interesting: in most cases one can set up a "successful" dinner party i.e. one can find groupings of 3 mutual `friends' or 3 mutual `strangers', described above, but there is one "unsuccesful" case where you cannot (which is why M=6 is the minimum to guarantee success). (Note: we define whether actors "know each other" at these dinner parties not in the usual social way, but solely on whether they have co-starred in movies)

buck wrote:PROBLEM: What is the minimum number of people needed at a party to ensure that either 5 people know eachother (that is, among these 5 people all of them know eachother) or 5 people don't know eachother?