1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.