Seating Guests at a TableDate: 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 |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/