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.
asked Oct 30, 2017 in Word Problem Answers by Mary

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
To avoid this verification in future, please log in or register.

1 Answer

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.

answered Jul 4 by Rod Top Rated User (570,500 points)

Related questions

1 answer
asked Jun 10 in Pre-Algebra Answers by Subarna Das (440 points) | 20 views
1 answer
Welcome to MathHomeworkAnswers.org, where students, teachers and math enthusiasts can ask and answer any math question. Get help and answers to any math problem including algebra, trigonometry, geometry, calculus, trigonometry, fractions, solving expression, simplifying expressions and more. Get answers to math questions. Help is always 100% free!
81,478 questions
85,655 answers
2,171 comments
69,137 users