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 https://cs.stackexchange.com/questions/67832/game-tournament-program-np-complete/67864#67864 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?

  • I believe this is a Transversal Design... It has been a while since I have worked with problems like this, but if you read up on Combinatorial Designs, I think you will find your solution. – InterstellarProbe Sep 14 at 12:50

The problem is readily solved for $N=q^2$ people with $q$ tables and $q$ chairs each if $q$ is a prime power:

Let $F$ be a finite field order $q$. We identify the tables (as well as the seats per table) with elements of $F$ and the people with elements of $F^2$.

For the $q-1$ possible picks for $a\in F^\times$, we can make a seating arrangement such that $(x,y)$ occupies seat $x$ at table $y+ax$. This is a bijection between people and chairs, i.e., nobody has to sit on someone else's lap nor is a seat leaft vacant: Seat $u$ at table $v$ is given to $(u,v-a^{-1}u)$ and no-one else.

In an extra round, we can place $(x,y)$ at seat $y$ at table $x$. Again, this bijects people with available seats.

We can tell exactly when $(x,y)$ meets $(x',y')$: If $x=x'$ they meet at table $x$ in the extra round. Otherwise, they meet in round $a$ for which $y+ax=y'+ax'$, i.e., when $a=(y-y')(x'-x)^{-1}$.

  • This gives 8 rounds though right? The OP was asking about if 9 rounds was possible. – Steve D Sep 14 at 14:23
  • Yes, now that I think about it more, I am convinced $a=0$ works, and that fully solves it. – Steve D Sep 14 at 14:39

Maybe interesting to see

http://mathworld.wolfram.com/SocialGolferProblem.html

http://www.mathpages.com/home/kmath388.htm

and these tables

https://web.archive.org/web/20050407074608/http://www.icparc.ic.ac.uk/~wh/golf/solutions.html#5-5-6

at 8 groups of 8 golfers for 9 weeks,

and the work of Ivan Dotu and Pascal Van Hentenryck

https://pdfs.semanticscholar.org/1070/d2f978fead4045b53640743a018ae518cccd.pdf

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.