3
$\begingroup$

In each of four months (eg. Jan, Feb, Mar, April) four tables of four guests meet for a four course dinner. Rule 1: Each guest brings a different course each month and Rule 2: the guests NEVER dine with the same guest more than once and Rule 3: a guest never brings the same dish more than once. That said, the monthly table number (1 thru 4) is not constrained and can repeat. Rule 4: Location of the table is driven by the main dish guest in whose home the dinner occurs. Thus it follows that a guest only hosts once during the four months.

For example: January, in guest 1's home she provides the main dish. In Feb guest 1 will bring the salad to another guest's home. Mar - guest 1 brings the desert to a third location, and in April the vegetable to still a fourth home. Each monthly table will have four unique guests, each of whom will bring a unique course.

This seems like it should be a simple combination problem because the variables are grouped in fours: four monthly dinners of four guests and four courses. I am having a terrible time trying to make unique combinations of guests such that no single guest dines with any other guest during any of the four monthly dinners.

If the number of guests is greater than 16, say 20 so that there could be five monthly tables will I need five months and five courses to complete the rotation? Clearly I am having trouble interpreting the real world problem into the appropriate mathematical context. HELP! Thanx!

$\endgroup$
1
  • 1
    $\begingroup$ This sounds a bit like the "social golfer" problem, which see, though with more conditions. It also sounds a bit like making an order 4 projective plane, another keyphrase that may reward a search. $\endgroup$ Jan 2, 2013 at 2:02

1 Answer 1

2
$\begingroup$

For the case of sixteen diners a four month schedule may be constructed from the five parallel classes of this Answer, using the fifth class to determine the dish assigned to a diner.

That is, let the four months' groupings be as in the first four days or "rounds" of that group tournament question.Then assign the "main" dish (and hosting responsibility) to the first group of the fifth class in January, to the second group of that class in February, to the third group in March, and to the fourth group in April.

Rotate the other three course/dish assignments similarly. For example, in January an appetiser would be brought by those who will bring a main dish in February, a vegetable by those who will bring a main dish in March, and the dessert by those hosting in April.

In this fashion each diner shares exactly one meal with twelve other diners (but no meal with the three diners whose dish assignments agree). Each diner hosts once and is responsible for each type of dish preparation once over the span of four months.

These kinds of arrangements are called resolvable block designs, and while a lot of them have been constructed, you'll find they exist only for special numbers of diners (points) and groups (blocks).

Added:

Let's take a look at the next larger design with similar features, 25 diners with five dish courses and a five month schedule, eating together in groups of five.

The design uses a complete set of mutually orthogonal latin squares of order 5, or what is equivalent and convenient for this case, an orthogonal array (OA) of 25 runs, strength 2, 6 "factors" and index 1.

What this amounts to is a list of twenty-five rows and six columns in which entries 1 through 5 are distributed so evenly that any two columns provide all twenty-five possible pairs. We add a letter A to Y for each participant to each row of a suitable OA library example (Wayback Machine):

A: 1 1 1 1 1 1
B: 1 2 2 3 4 5
C: 1 3 3 4 5 2
D: 1 4 4 5 2 3
E: 1 5 5 2 3 4
F: 2 1 2 2 2 2
G: 2 2 3 5 1 4
H: 2 3 5 1 4 3
I: 2 4 1 4 3 5
J: 2 5 4 3 5 1
K: 3 1 3 3 3 3
L: 3 2 5 4 2 1
M: 3 3 4 2 1 5
N: 3 4 2 1 5 4
O: 3 5 1 5 4 2
P: 4 1 4 4 4 4
Q: 4 2 1 2 5 3
R: 4 3 2 5 3 1
S: 4 4 5 3 1 2
T: 4 5 3 1 2 5
U: 5 1 5 5 5 5
V: 5 2 4 1 3 2
W: 5 3 1 3 2 4
X: 5 4 3 2 4 1
Y: 5 5 2 4 1 3

The six columns can be used to determine the five month schedule of dining partners and the rotation of dish/course assignments however we like. For example, we can interpret the first five columns as defining which groups of five eat together in the respective five months of the schedule. That leaves the sixth and final column for use in determining what dish each person brings. Add the entry of the sixth column to the number of the month and reduce mod 5:

Course:    (column(6) + # of month) mod 5 
  main                     0              
  appetiser                1              
  salad                    2              
  vegetable                3              
  dessert                  4              

The existence of such "complete" designs is known only for orders that are powers of primes, e.g. the cases 4 and 5 discussed above, which in turn require the square of that order in participants or "runs" to use the OA term. It is a famous conjecture that these are the only such possibilities. Stated more precisely, we'd like to know if all "projective planes" are of prime power orders.

Further Reading:

Mutually orthogonal latin squares

Orthogonal array

Projective plane

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .