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?

  • $\begingroup$ 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. $\endgroup$ – InterstellarProbe Sep 14 '18 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}$.

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

Maybe interesting to see



and these tables


at 8 groups of 8 golfers for 9 weeks,

and the work of Ivan Dotu and Pascal Van Hentenryck


  • $\begingroup$ Great, though they don't explain how to solve it $\endgroup$ – skan Sep 14 '18 at 23:00
  • $\begingroup$ Another reference: metalevel.at/sgp $\endgroup$ – cgiovanardi Sep 15 '18 at 9:03
  • $\begingroup$ Stangely two of the links give different solutions one of the problems: 8 groups of 4 players gives 9 weeks here web.archive.org/web/20050407074608/http://www.icparc.ic.ac.uk/… but gives 10 weeks here metalevel.at/sgp What's wrong? Are the other solutions well? (for example for 8 groups of 8 players) $\endgroup$ – skan Sep 15 '18 at 17:45
  • $\begingroup$ Any news? Why the two links provide contradictory information? $\endgroup$ – skan Sep 21 '18 at 10:20

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.