I am organizing a dinner for 16 guests in a dining room with 4 tables of 4 seats. There are 5 courses in which the guests may change seats.
Is it possible to devise a seating arrangement such that every guest joins a table with every other guest?
There are 16*15/2 = 120 combinations required and at each course there are 4*4*3/2=24 combinations realized, so the maximum possible number of combinations that can be realized in 5 courses is 24*5 = 120, which is just enough.
My question is how to proceed and find an algorithm for this table arrangement problem if a solution exists.
I found the solution myself searching the internet, in Annals of discrete mathematics 1989 (42):65-73. Hartman (ed), wherein the Steiner system S(2,4,16) was listed, see https://en.wikipedia.org/wiki/Steiner_system.
In C, the solution can be represented as:
const int NGuestTab = 4; const int NTable = 4; const int NRound = 5;
int NGuest = NTable * NGuestTab;
enum GType {A1,A2,A3,A4, B1,B2,B3,B4, C1,C2,C3,C4, D1,D2,D3,D4};
// Steiner system S(2,4,16)
int Sol[NRound][NTable][NGuestTab] = {{{A1,A2,B1,B2},{A3,A4,B3,B4},{C1,C2,D1,D2},{C3,C4,D3,D4}}, {{A1,A3,C1,C3},{A2,A4,C2,C4},{B1,B3,D1,D3},{B2,B4,D2,D4}}, {{A1,A4,D1,D4},{A2,A3,D2,D3},{B1,B4,C1,C4},{B2,B3,C2,C3}}, {{A1,B3,C4,D2},{A2,B4,C3,D1},{A3,B1,C2,D4},{A4,B2,C1,D3}}, {{A1,B4,C2,D3},{A2,B3,C1,D4},{A3,B2,C4,D1},{A4,B1,C3,D2}}};