N=64 hungry diners come to a buffet.
We sit them at 8 different (s=8 people at each table) tables so that they get to know each other while they eat.

After a while we distribute them over the tables so that no one will ever match another person with whom they have eaten before.
We keep on redistributing them with different while they eat.

What is the maximal number of rounds each person can do?

Intuitively I would say the solution is rounds=(N-1)/(s-1)=9 but I don't know if it applies always nor if take into account all restrictions.

The same problem can be thought as a group of poker players playing against each other.
If the problem were smaller, 16 people in groups of 4 the solution would be 5 rounds:

a1 a2 a3 a4 - b1 b2 b3 b4 - c1 c2 c3 c4 - d1 d2 d3 d4
a1 b1 c1 d1 - a2 b2 c2 d2 - a3 b3 c3 d3 - a4 b4 c4 d4
a1 b2 c3 d4 - b1 a2 d3 c4 - c1 d2 a3 b4 - d1 c2 b3 a4
d1 b2 a3 c4 - b1 d2 c3 a4 - c1 a2 b3 d4 - a1 c2 d3 b4
a1 d2 b3 c4 - b1 c2 a3 d4 - c1 b2 d3 a4 - d1 a2 c3 b4 

But I don't know how to do it for a larger problem apart from bruteforce, at least for the simpler case N=s^2.

Here Game tournament program, NP complete? a solution is given just for the case of subroups of 4.

How would you address this problem computationally?
How would you do it theoretically in a simple way?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.