Seating Guests at a Table

Date: 9/5/95 at 16:57:39
From: Dana Murray
Subject: Diners for Courses, how to seat them ?

Good morning Dr Math,

Consider seating n dinner guests at k tables of l (lower case L) settings 
each, therefore n = k l , for m courses so that no guest shares a table more 
than once with any other guest.  

Equivalently, consider n players to be divided into k teams of l players for 
m rounds of a contest.  No player may, more than once, be on the same team 
as any other player.

1. What is the maximum value of m, as a function of k and l ?

2. How could one systematically specify the seating arrangement for the m 
courses ?

Thank you for your trouble.

Dana Murray

Date: 9/24/95 at 1:31:38
From: Doctor Andrew
Subject: Re: Diners for Courses, how to seat them ?

Neat problem.  I think the second question is very much related to the first.
I thought of a useful analogy to this problem.  Imagine that you start off
with a tangle of string with n knots, each knot representing a guest.  Now,
at the beginning, let each knot be connected to every other knot by a piece
of string.  Whenever two people (two knots) sit together at a table,
cut the string between the knots representing those people.  At the start
there are (n choose 2) links of string (the number of pairs at the meal
which is n!/(2!(n-2)!) = n(n-1)/2 if you've done some probability).  At each
course, at each table, each person is sitting with (l-1) other people.  So,
(l-1) strings connected to each knot will be cut, or m*(l choose 2) knots
will be cut. (The number of pairs of people at each table).  This number
is ml(l-1)/2.  So, at this point we have an upper bound on the number of 
courses.  If you divide the number of strings by the number that must
be cut each turn, you'll get a limit on how many courses, because after
that many courses there will be no strings left to cut (and hence no
pairs of people that have not sat together at a table).

There is another limitation, however, that will keep you from easily
achieving this upper limit.  You can imagine that as this tangle of knots and 
string gets cut up, pieces will start to come off it.  A whole set of knots
could be connected to one another, but get disconnected from the mass
of the tangle.  If this set has less than l knot in it, then you 
are in trouble.  For each knot (person) in this set, you cannot find
(l-1) other people who are connected to it (who have not sat with him/her).

I hope this knot metaphor helps and it's not too late.  If it is too late,
we'd be glad to hear how you solved the problem.  In trying to get back
to you as fast as we can, we don't have a solution yet (an algorithm
that will maximize the number of courses), but if I were to look for one
I would try to find one that does NOT cut up the tangle into smaller chunks.
Such an algorithm would probably make the cuts fairly evenly, preventing any
set of knots from having less connections to the rest than any other set of
knots of the same size.

Good luck!  Boy, if I didn't have so much algebra homework I'd love to
spend more time on this one.

- Dr. Andrew

Date: 9/27/95 at 19:48:40
From: Doctor Andrew
Subject: Re: Diners for Courses, how to seat them ?

I've been working on your problem, and here is what I've come up with.
I couldn't get this one and couldn't find it in any books, so here's what
one of my Professors, Professor Grinstead, said when I asked him about it.  

As background for Professor Grinstead's answer, the limit on how many 
courses can be served is (m-1)/(l-1), since for every diner there are 
m-1 people s/he can dine with and at every course s/he can dine with l-1 
less:

Here's what Professor Grinstead said:

        [This] problem can be phrased in terms of graphs.  We consider
the complete graph G on ml vertices, where the vertices represent the
people.  A 'course' consists of a set of m vertex-disjoint complete
subgraphs each of size l.  Let C be this disjoint union of complete
subgraphs.  A rephrasing of the given question is:  Given G, how many
mutually edge-disjoint copies of C can we find in G?

        The answer to this question is not completely known.  However, one
can give a partial answer which is interesting.  The prettiest case is the
case where each person sits with every other person EXACTLY once in the set
of courses, i. e. every edge in G occurs in EXACTLY one of the copies of C.
Note that every vertex in C is of degree l-1, and every vertex in G is of 
degree ml-1. 

Thus, a necessary condition for the existence of such a collection of
copies of C is that (l-1) divides (ml-1).  There is a celebrated theorem of
Richard Wilson (proved in the 1970s) that implies that this necessary
condition is asymptotical sufficient, i.e. that if l is considered to be
fixed, then for sufficiently large m, such a configuration exists.  I do
not think that it is easy to determine how large 'sufficiently large' is,
but it should be possible (although probably nobody reading this cares). 
Of more importance is the fact that the above theorem is existential, i.e.
it does not give a method for actually constructing such configurations.

        Of course, for most pairs (l, m), it is not the case that (l-1)
divides (ml-1).  What can be said in this case?  Not a lot, but one can
decrease m until this condition is true, and then assert that such a
configuration might exist (since we don't know whether m is 'sufficiently
large').  For example, if l = 6, and m = 27, then 5 does not divide ml-1 =
161, but 5 does divide (26)(6) - 1 = 155 (here, m has been lowered to 26). 
This gives 31 courses for these 26 people (31 = 155/5), assuming that 26 is
'sufficiently large'.  The maximum number of courses one could ever have
with m = 27 and l = 5 is 32 (= (ml-1)/(l-1)) so the achieved number of
courses is only one less than the maximum possible.  It must be admitted
that in this example, one person doesn't ever eat, but that can be fixed by
starting with the configuration for 26 people, and switching in the 27th
person for a few courses.
------
Professor Grinstead did not know of any algorithm offhand.  It would be
possible to have a computer search all possibilites and return one that
works; however, this wouldn't be very efficient.  I hope this helps.
If we come across such an algorithm, we'll send it to you.

-Doctor Andrew,  The Geometry Forum

Date: 10/1/95 at 1:0:50
From: Dana Murray
Subject: Re: Diners for Courses, how to seat them ?

Dear Dr. Andrew,

Thank you very much for your TWO responses to my problem.  It is not often
that a doctor shows this much care for his patients.  

There is something I don't understand in your answers, and, since you
invited me to tell you what I have done, I will do so.  Thank you.

1.  Question

In your above response I don't see the symbol k, the number of tables.  My
feeling is that k should play a role somewhere.  Also, in your paragraph
*As background ...*  you use the symbol m (number of courses) in an
expression for a bound on the maximum number of courses.  Maybe I am missing 
something, or we could possibly be using different notation.

2.  My humble attempt 

Notation

   k   number of tables
   l   seats per table  (lower case L)
   n = k l  number of people

Let the seating arrangement for a course consist of assigning pairs (t,s),
to each of the n people, such that, of course, t=1,...,k and s=1,...,l.  One
could improve on the notation using an index i=1,...,n to designate the
individuals and j=1,...,m to designate the course numbers.  Since I can't
use subscripts here I won't try including i and j.  In any case I give an
example below.

My heuristic table assignment:  The first course (j=1) is assigned
arbitrarily.  For the (j+1)-st course every person goes to the table number
being the sum of his table and seat numbers at the j-th course.  Everyone
goes to the next higher seat number. (This does not appear to be essential,
but somehow it keeps things evenly spread out)

Please note.  
For table numbers greater than k, one subtracts k.  Similarly for seat numbers.

Seat numbers need not be physical numbers.  Although they are really virtual
numbers, one needs some mechanism to force current table partners to
different tables for the next course.

Example 1

   k = 2 tables,  l = 2 seats per table,  thus  n = kl = 4 people

 Person   Course    Course
  index     1         2
   1      (1,1)     (2,2)
   2      (1,2)     (1,1)
   3      (2,1)     (1,2)
   4      (2,2)     (2,1)

Please note again.  The nice thing is that one need not arithmetically apply
the algorithm for subsequent courses, but could simply look up the
transitions of pairs (t,s) for the first to the second course.

For the third course persons 1 and 2, who shared table 1 on the first
course, will again be seated together, but at table 2.  

NOW FOR THE REAL PROBLEM ...

The real problem was to seat kids at a camp in order to maximize the
opportunity of meeting new people.  A complication was that the number of
boys and girls had to remain evenly spread.  The youth leader who posed this
problem said that boys eat more than girls and too many boys at a table
would leave them starved :-))

The above algorithm was applied to 80 (kids) = 8 (seats) x 10 (tables).  

Thank you for your trouble.  I appreciate your time.

Dana Murray
dana@aot.co.za

Date: 10/8/95 at 1:48:1
From: Doctor Andrew
Subject: Re: Diners for Courses, how to seat them ?

Sorry we didn't get back to you sooner.  This is a hard problem and we
really can't give you a very good answer.  We'd be glad to hear how well
your algorithm worked.  There is one insight I had that could help construct
an algorithm.  If you are going to eat at a table with someone else in the
future then it is better if you have dined with a lot of the same people
already.  Otherwise, you have fewer ways of dining at a table with that
person (less people are available who can sit at that table).  I think by
removing the constraint that two people CAN'T eat together twice, the
problem becomes more workable.  It probably isn't as difficult to come up
with an algorithm that reduces how often the same people share a table.
This is the sort of problem that a neural network could probably work really
well for.  You could just sit back while it figured out a good way to use
the information of who has eaten with who into a seating assignment.  But
that's another story.

With only a small number of people (80 for instance), a computer could 
reasonably test all the alternatives and come up with a plan.  If you've 
done any programming before, I'd be glad to help you write a program to do 
this.

-Doctor Andrew,  The Geometry Forum