Seating arrangement problem, 16 guests, 4 tables, 5 courses

Question

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.

Answer 1

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}}};