2
$\begingroup$

During a dinner with $k=20$ persons sitting at $n=4$ tables with $m=5$ seats, everyone wants to share a table with everyone. The assembly decides to switch seats after each serving towards this goal. What is the minimal number of servings needed to ensure that everyone shared a table with all the other persons at some point during the dinner? And what is the optimal switching strategy?

An extension to generic $(k,n,m)$ with $k\le mn$ would also be nice.

  • 1
    Designs that accomplish this are called the [Social Golfer Problem](http://mathworld.wolfram.com/SocialGolferProblem.html).2012-04-11
  • 0
    It is easy to show that with the given parameters, at least five courses are necessary. During each course, one fixed diner eats with four others, and if all 19 others were to share a table with this one, we'd need at least the ceiling of 19/4 = 5 courses.2012-04-11
  • 0
    Yes, I gathered as much. My conjecture at the moment is that one needs 7 courses.2012-04-11
  • 1
    @hardmath The Social Golfer Problem you link to is about making sure that each player plays *no more* once with each person. That is different from this problem.2012-04-11
  • 2
    Theorem 1.52 in [this Handbook of Combinatorial Designs chapter](http://www.ccrwest.org/gordon/hcd.pdf) by Gordan and Stinson implies that 6 courses suffice. In the notation there your problem requires $r(4,5)$ courses because the 2-(20,5,1) covering is to be resolvable (partitionable into parallel classes).2012-04-11
  • 0
    @ThomasAndrews: Yes, the problem I linked to was a "packing" problem. This one is a "covering" problem. Sometimes the parameters allow a resolvable BIBD that answers both, but not here.2012-04-11
  • 0
    What about a constructive algorithm to design the table arrangement across courses?2012-04-11
  • 0
    The number of ways of assigning 20 people to the four tables (in one course) is 488,864,376. While we can arbitrarily fix the assignment for one course, I suspect a little study will speed our way to a solution (rather than brute forcing our way).2012-04-12
  • 0
    @hardmath: I found $20!/(5!)^4 4!=488,864,376$ as well. Brute force is not really possible but a branching algorithm should work better, when keeping track of how many persons each person has met more than once. If this number is larger than 5, the allocation series is not valid.2012-04-12
  • 2
    Warning: too many of these multiple course dinners may lead to obesity.2012-04-12

1 Answers 1

4

A six course solution is given in Table A.1 of the Appendix to the paper Equitable Resolvable Coverings by van Dam, Haemers and Peek (2002):

1st course: 18 20  3  2 17 11 16  6 15 12  7  9 14  8 10  5  4 13  1 19  2nd course: 16 18  1 14  3 11  5 20 10  4 17 12 19  9 15  6  7  2  8 13  3rd course: 10  6 18 13 12 19 17  3  8 11 14 20  7  1 15  2  4  5  9 16  4th course:  5  4  3 12  7  6 16 19 20  8 10 17  1  2 15  9 11 13 18 14  5th course:  7 18 19 11  2  5 14 17  4  6  8 20  1  9 12 13 16  3 15 10  6th course: 13 17  7 16 20 14 10 19 12  2  5 18  4 15  8  6  1  3 11  9 

The authors say this covering "was found by the computer in less than a minute" by simulated annealing, some details of which are in Sec. 4 of their paper.

Curiously this covering is not what the authors define as "equitable" as in the paper's title, namely that each pair appears together only once or twice. Elsewhere in the paper they report that a minimum equitable resolvable 2-(20,5,1) covering has seven parallel classes, rather than the six shown above. For that see Table A.6 in their Appendix.

  • 0
    Thanks, I was considering implementing a simulated annealing algorithm this afternoon...2012-04-12
  • 1
    If you aren't already familiar with it, the [La Jolla Covering Repository](http://www.ccrwest.org/cover.html) is a neat resource for many things related to covering designs. The site was reorganized a couple of years ago, and I can no longer find some of the papers Dan Gordan had coauthored there, but the Links link on that page goes (among other places) to his home page, where links to his research papers are organized by topic. In any case the survey I pointed you to in the Comments above has a citation to Nurmela and Östergård's paper on simulated annealing in this context.2012-04-12
  • 0
    Thanks for the answer and the additional links. (Combinatorics is far from my expertise area!) I reprogrammed a simulated annealing algorithm and found a solution in a few minutes indeed. (To be [posted there](http://xianblog.wordpress.com/2012/04/14/not-le-monde-puzzle-solution) tomorrow.)2012-04-13