# Combinatoric puzzle: minimum servings at dinner

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.

-
Designs that accomplish this are called the Social Golfer Problem. – hardmath Apr 11 '12 at 16:39
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. – hardmath Apr 11 '12 at 16:51
@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. – Thomas Andrews Apr 11 '12 at 17:00
Theorem 1.52 in this Handbook of Combinatorial Designs chapter 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). – hardmath Apr 11 '12 at 17:22
Warning: too many of these multiple course dinners may lead to obesity. – Doug Spoonwood Apr 12 '12 at 11:39

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.

-
Thanks, I was considering implementing a simulated annealing algorithm this afternoon... – Xi'an Apr 12 '12 at 19:16
If you aren't already familiar with it, the La Jolla Covering Repository 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. – hardmath Apr 12 '12 at 19:46
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 tomorrow.) – Xi'an Apr 13 '12 at 7:02