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.

  • 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 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