In fact, with 16 couples, 4 to a dinner (thus, 4 dinners per month), and 5 months, we can even achieve near perfection in hosting, by which I mean:
A) Each couple will dine with each other couple precisely once
B) Over the first 4 months, each couple will host precisely once. For the last month, the celebratory dinners will be at fancy restaurants rather than hosted by any particular couple.
Again, I’ll leave this as a puzzle for now, in case anyone would like to figure it out on their own.
If I understand correctly:
there will be twelve dinners in total (three a month for four months)
there are twelve couples
each couple will host one dinner
each dinner have a total of four couples (the hosts plus three others)
The following arrangement seems equitable: all twelve couples will attend the same number of dinners (four), each dinner will have a unique combination of couples, and each couple gets a turn hosting. The only flaw is that some couples never dine together (is that a requirement?)
Say that the couples are numbered 1-12. The first number is the host couple, and the other three the guests:
[ul]
[li]1, 2, 3, 4[/li][li]2, 3, 4, 5[/li][li]3, 4, 5, 6[/li][li]4, 5, 6, 7[/li][li]5, 6, 7, 8[/li][li]6, 7, 8, 9[/li][li]7, 8, 9, 10[/li][li]8, 9, 10, 11[/li][li]9, 10, 11, 12[/li][li]10, 11, 12, 1[/li][li]11, 12, 1, 2[/li][li]12, 1, 2, 3[/li][/ul]
The preceding list can be shuffled if you need flexibility in scheduling.
Lumpy, the problem is trying to avoid as amny duplications as possible. The goal is to avoid same couples from having dinner together or keep it to a minimum. Also several couples in your solution did not have dinner together. Goal is to have as many as possible mmet as many as possible.
That would be an affine plane of order 4.
Err… that’s worse than I thought. Not only does each couple dine with only five others, but but they dine with some of the five more than others. Ok, I admit, there’s got to be a better way.
Very good! We can take the couples to be the points of the plane and the dinners to be the lines of the plane. A couple is part of a particular dinner if the point lies on that line, and dinners take place at the same time if their lines are parallel.
As for the hosting, we select one “celebratory” (i.e., non-hosting) month and a bijection to the non-celebratory months from the dinners during the celebratory month. A couple hosts the dinner they attend in the month corresponding to the dinner they attend during the celebratory month.
Note that it’s not possible to do without the celebratory month, except degenerately:
Let C be the number of couples, T the number of dinners (overall), M the number of months, D the number of couples per dinner, and P the number of dinners per month, with each couple eating one dinner each month, and each couple dining with each other couple exactly once.
We must have that C = D * P, as each couple eats one dinner each month. Thus, C must be a multiple of D.
We must also have that C - 1 = M * (D - 1), as these both count the number of other couples any given couple dines with. Thus, C must be one greater than a multiple of M.
Finally, we must have that C * M = T * D, as these both count (couple, dinner) pairs where the couple attended the dinner. But if each couple hosts exactly once, we will also have that C = T. Thus, either there are no couples and no dinners, or we will have M = D, which with the above, will tell us that M must be 1, and thus there is just one couple, eating one dinner, which they host, with no guests.
So the affine plane solution is as good as it gets! Luckily, we can readily pull it off whenever D is a prime power, with C as its square.
Who said they dine with each couple exactly once? Obviously there would be six couple pairs that each meet twice.
There may be a relatively simple proof (I have a somewhat tedious proof), but I think you’ve left out a few steps.
I see that people are still trying to come up with solutions, even though my two posts at the top explain how to get as close as possible. It looks like I didn’t get the constraints right, but it’s still a useful system because once you know that it works for one couple it works for all of them because everything works the same for each couple. This is one that works with only one duplication: n = 12, x = 1, y = 3, z = 7:
1: 1, 12, 10, 6
2: 2, 1, 11, 7
3: 3, 2, 12, 8
4: 4, 3, 1, 9
5: 5, 4, 2, 10
6: 6, 5, 3, 11
7: 7, 6, 4, 12
8: 8, 7, 5, 1
9: 9, 8, 6, 2
10: 10, 9, 7, 3
11: 11, 10, 8, 4
12: 12, 11, 9, 5
The case of P[sup]2[/sup], P prime is pretty trivial, but this is more interesting. Are there solutions if and only if P is a power of a prime? (Is “only if” unproven?)
I did find some discussion with figures on-line
This does achieve the minimal duplication which I conjecture is impossible.
HOWEVER it violates one constraint which I think is essential to OP’s problem: Each couple must dine exactly once each month. There’s no way to arrange your dinners without having some couples eating twice in a month, while others go hungry.
You’re right…
The first two couples per dinner are easy: start at 1 and 4, respectively. The third is also ok, start at 8:
M1D1: 1, 10, 6
M1D2: 2, 11, 7
M1D3: 3, 12, 8
M2D1: 4, 1, 9
M2D2: 5, 2, 10
M2D3: 6, 3, 11
M3D1: 7, 4, 12
M3D2: 8, 5, 1
M3D3: 9, 6, 2
M4D1: 10, 7, 3
M4D2: 11, 8, 4
M4D3: 12, 9, 5
This leaves 4, 5, 9 unassigned at month 1; 7, 8, 12 at M2; 3, 10, 11 at M3 and 1, 2, 6 at M4. However, 4, 5 and 9 all have a conflicts at all available positions for M1. And it’s going to get worse from there as the choices for M1 constrain the subsequent months.
So I’d say: make a schedule for the three first couples per dinner so that those don’t duplicate, and then let the three unassigned ones choose whichever dinner they want to join that month without trying to optimize any further.
Unfortunately, it won’t be possible for everyone to have dinner with everyone with this added constraint. (At least, not that I can figure out.)
One way to construct an “affine plane” is like so: take a finite field F, and consider the two-dimensional vector space F[sup]2[/sup] over it. Let points be the elements of this vector space, and let the line containing points p and q be the set {p * f + q * (1 - f) | f in F}, as usual.
What remains is only to show that we can obtain a finite field for every prime power size. In fact, there is a unique finite field for every prime power size and there are no other finite fields. For prime size p, the construction is easiest: as you no doubt realize, it is the integers modulo p. For prime powers p[sup]n[/sup] more generally, the construction is less obvious; one takes the solutions to x[sup]p[sup]n[/sup][/sup] = x within the algebraic closure of the integers modulo p. (That every finite field has a prime power size follows from the fact that each finite field has a subfield 0, 1, 1 + 1, 1 + 1 + 1, etc., which must be the integers modulo some prime. That the aforementioned construction yields the only finite fields follows from the appropriate generalization of Fermat’s little theorem.)
(In particular, the four-element finite field can be thought of as 0, 1, 2, and 3, with addition as bitwise XOR and multiplication such that 0 and 1 act as usual, while 2 and 3 are inverses and square to each other.)
One can also axiomatize the relevant properties of affine planes purely combinatorically, as a structure with points, lines, and line directions, where every line has a unique direction (and there are at least two directions), every two points determine a unique line (and each line has at least two points), and every direction and point determines a unique line. The planes constructed from fields as above satisfy these axioms, and are called “Desarguesian”. It turns out there are also finite non-Desarguesian affine planes, but every known example has the same size as a Desarguesian example; it is indeed an open question whether there are any others.
Stupid clunky server keeping me from editing… Replace the previous post with this:
One way to construct an “affine plane” is like so: take a finite field F, and consider the two-dimensional vector space F[sup]2[/sup] over it. Let points be the elements of this vector space, and let the line containing points p and q be the set {p * f + q * (1 - f) | f in F}, as usual.
What remains is only to show that we can obtain a finite field for every prime power size. In fact, there is a unique finite field for every prime power size and there are no other finite fields. For prime size p, the construction is easiest: as you no doubt realize, it is the integers modulo p. For prime powers p[sup]n[/sup] more generally, the construction is less obvious; one takes the solutions to x[sup]p[sup]n[/sup][/sup] = x within the algebraic closure of the integers modulo p. (That every finite field has a prime power size follows from the fact that each finite field has a subfield 0, 1, 1 + 1, 1 + 1 + 1, etc., which must be the integers modulo some prime. That the aforementioned construction yields the only finite fields follows from the appropriate generalization of Fermat’s little theorem.)
(In particular, the four-element finite field can be thought of as 0, 1, 2, and 3, with addition as bitwise XOR and multiplication such that 0 and 1 act as usual, while 2 and 3 are inverses and square to each other.)
One can also axiomatize the relevant properties of affine planes purely combinatorically, as a structure with points, lines, and line directions, where every line has a unique direction (and there are at least two directions), every two points determine a unique line (and each line has at least two points), every direction and point determines a unique line, and any two lines of different directions meet at a unique point. The planes constructed from fields as above satisfy these axioms, and are called “Desarguesian”. It turns out there are also finite non-Desarguesian affine planes, but every known example has the same size as a Desarguesian example. It is an open question whether there are any other non-Desarguesian affine planes.
In that sense, the “only if” you ask about is indeed unproven. That having been said, it’s not obvious to me that every solution to problems of the OP’s type is such that we would need the property that every two lines of different directions meet at a point. Indeed, if we forget about the hosting requirements, this is clearly unnecessary; we could, for example, consider affine spaces of dimension greater than 2 and still pull off the property that every two couples (i.e., points) share a unique dinner (i.e., line).
Ah, this is indeed necessary, as follows:
Suppose we fix a number of couples C and a dinner size D, and wish to arrange for each couple to eat once each month, each pair of couples to codine precisely once, each dinner prior to the last month to be hosted by one particular couple with the last month hosted by no particular couple [as noted before, we can’t do better than this], and each couple to host precisely once. [Also, let us demand there be more than one couple, thus ruling out the degenerate cases “zero couples considered as having as many dinners of zero size as you like for as many months as you like” and “one couple having dinner by themselves two months in a row, first hosting and then not hosting”]
The number of dinners a month P will be C/D, of course.
The number of months M will be just enough for any given couple to meet each other couple precisely once; that is, it will be (C - 1)/(D - 1).
Finally, the total number of dinners T will be P * M.
But the hosting requirement tells us that the total number of dinners must also be C + P [the hosted dinners plus the dinners in the last month]. So C + P = P * M.
Expanding this out in terms of C and D, and shuffling terms around, we find that this becomes the equation CD[sup]2[/sup] = C[sup]2[/sup].
So, we must have that C = D[sup]2[/sup] (and thus P = D, M = D + 1, and T = D[sup]2[/sup] + D).
Now, let us show that every two dinners during different months share a common couple (indeed, a unique one).
Pick two months, and consider the number of triples of the form (dinner from first month, dinner from second month, couple from both dinners). One way of counting this is to sum up, over all the dinner pairs, the size of their union; this will be P[sup]2[/sup] * (2D - average overlap of dinner pairs) = 2D[sup]3[/sup] - D[sup]2[/sup] * average overlap. Another way of counting this is to sum up, over all couples, the number of dinner-pairs containing them; this will be C * (2P - 1) = 2D[sup]3[/sup] - D[sup]2[/sup]. Equating these, we find the average overlap is 1. Note that the overlap can never be greater than 1 (as two couples uniquely determine a dinner); thus, we can conclude the overlap is always precisely 1.
Great. So we have that every dinner occurs in a particular month, every pair of couples share precisely one dinner, every month each couple attends a particular dinner, and every pair of dinners in separate months share a unique couple. (And there’s more than one dinner, each with more than one couple, by our nondegeneracy presumption). This is precisely the structure of an affine plane.
How about deciding who hosts when? As noted previously, one simple solution is to have the hosts during any given month drawn from a particular dinner during the last month. It’s not yet clear to me whether this is the only possible solution or whether there are others possible ways to handle the choice of hosts once everything else has been determined.
You guys have been a huge help with this. We had no idea how difficult it was just tring for a best answer.
This looks similar to something that I saw before about scheduling cross country teams into meets. The solution for 12 teams was a special case of a solution for 16 teams. It was done in 5 separate groupings, where each team met each team once. For the diners problem, it would look something like this:
Month 1
1, 2, 3, 4
5, 6, 7, 8
9, 10, 11, 12
13, 14, 15, 16
Month 2
1, 5, 9, 13
2, 6, 11, 16
3, 7, 12, 14
4, 8, 10, 15
Month 3
1, 6, 10, 14
2, 5, 12, 15
3, 8, 11, 13
4, 7, 9, 16
Month 4
1, 7, 11, 15
2, 8, 9, 14
3, 5, 10, 16
4, 6, 12, 13
Month 5
1, 8, 12, 16
2, 7, 10, 13
3, 6, 9, 15
4, 5, 11, 14
This can be modified for 12 people by crossing off numbers 13 through 16. If only 12 people are used, then month 1 would have 3 groupings of 4 couples. After that, the meetings would be 4 groupings of 3 couples. I didn’t put down who hosts each meeting, but some couples would have to host more than once and it wouldn’t be even. For 12 people, there would need to be 19 hosts. Even for 16 couples, there would need to be 20 hosts.
Note that Box, Hunter, and Hunter’s Design of Experiments gives no balanced incomplete block designs for 12 treatments. So trying to evenly distribute 12 people is not possible, except maybe a degenerate solutions of every possible combination.
For what it’s worth, the schedule mcgato has written out is the order 4 affine plane we’ve been discussing.