Given 4 tables and 5 rotations, how can I make a seating plan that ensures each of my 20 guests sits with everyone else at least once?

Question

I will have 20 guests for dinner. We will sit 5 per table. I will serve 5 courses and we will change seating for each course. I need a seating chart for each course so that by the end of the dinner each guest sat with every other guest at least once.

Answer 1

The simple answer is that you can’t do it. Here’s the reasoning. 

For the first course the guests can sit wherever they like. Once seated they are each allocated a letter of the alphabet from A to T.  This will help us to track the movement of each guest.

Each guest must sit with each other guest over 5 courses. That’s 19 “associations” over 5 courses, an average of 3.8 per course. So since there can only be 4 other guests at a table, 19=4×4+3, that is, 4 courses with 4 new associations and one course only for a single duplicated association. That implies a total of 20 duplications but since each duplication involves two guests there are only 10 duplicated combinations. 

If we monitor just the duplicated associations, we should see that every guest has only one duplicated association in order to meet the requirement of sitting with every other guest over 5 courses.

SEATING PLAN

	Course 1	Course 2	Course 3	Course 4	Course 5
Table 1	ABCDE	AEIMQ	AF	AG	AH
Table 2	FGHIJ	BFJNR	B	B	B
Table 3	KLMNO	CGKOS	C	C	C
Table 4	PQRST	DHLPT	D	D	D

In the seating plan we can see that for course 2, guests A, E, F, J, K, O, P, T have used up their single duplicated association, so in the remaining courses they must not duplicate any association. We can also keep the positions of A, B, C and D the same for the remaining courses. (In the second course, A, B, C and D can sit at different tables but E is forced to sit with a guest who was also on table 1. The same applies to J, O and T and tables 2, 3 and 4.)

We can start to put other guests on A’s table for the remaining courses, being careful not to create more duplicated associations with  F, J, K, O, P, T as well as E. So we have AF, AG and AH for courses 3, 4 and 5. We already have AI in course 2, so we need to put J somewhere. J is one of the guests who is not allowed any more duplications. But J has already been associated with F, G and H in course 1, and is not allowed any more duplications. Since J can’t sit on table A for any course, A cannot sit with every other guest. The same applies to O and T for table A. The best that can be hoped for for A is 16 out of 19 associations. What applies to A also applies to the other guests. So in 5 courses it isn’t possible for each guest to sit with each of the other guests. A 6th course would be needed to allow each guest to sit with each other guest.