I copy and pasted this from a friend who is looking for best possible answer.
Help…I have a mathematical brain teaser for a real life situation. Marianne and I are part of a dinner club involving 12 couples in total. We would like to meet for dinner once a month in groups of 4 couples. So there would be 3 separate dinner venues each month. We will do this for 4 consecutive months… Which would create 12 total dinners…each hosted by one of the 12 couples. Herein lies the challenge:
Determine the best combination of dinner couples over the 4 month period that will maximize even distribution with the least amount of duplications and misses. Sounds easy, but I can assure you it has already been the cause of several headaches. Please feel free to send this on to your brainy friends.
H E L P!!!
I haven't touched it yet but his solutions are worse than he had hoped for.
Every couple attends the dinner with their number and the dinner with their number + x and their number + y. (If the number gets over n, deduct n). x and y should be chosen such that the number of weeks between dinners is roughly equal, and also such that x and y are not divisible by each other and x * y > n.
Ok, edit window expired as I tried to update my post for 4 rather that 3 couples per dinner. So here it is:
The dinners are numbered 1 through n.
The couples are also numbered 1 through n.
Every couple attends the dinner with their number and the dinner with their number + x, their number + y and their number + z. (If the number gets over n, deduct n). x, y and z should be chosen such that they’re not divisible by each other and also not by the difference between them and n. (I.e., 5 and 7 don’t work because 7 = 12 - 5.) And x * y * z > n.
I can’t make it work for 12 dinners with 4 couples, you end up with at least some duplication. Maybe with 13 or 14 dinners it’ll work.
Realistically, not everybody is going to be free every night, so you need people’s “not this date” lists, and their preference for going to a dinner with duplication, or skipping dinner with just one duplication (promise never more than one duplication; that’s probably feasible). Ask if anyone would like to attend an extra one if an extra couple is needed. Ask if anyone would mind hosting an extra dinner if need be. Promise confidentiality.
Then apply iljitsch’s equation, and make adjustments for schedules. Make further adjustments for preferences RE: duplications and missing or attending an extra time. Cross fingers.
Twelve dinners, and four couples each , there’s 48 places. So each couple can only attend four dinners.
When you attend a dinner, you are there with 3 other couples at each dinner, and you then attend four dinners, you therefore eat with a total of 12 couples.
But there are only 11 other couples, so you must repeat with one other couple … And that goes for all other couples, they only repeat with one couple… If couple Q repeats with extra couples then they must miss out on meeting some other couple for each extra repeat.
So thats the easy way to spot fairness/evenness …Each couple has only one “repeat” couple.
Suppose you are contriving some matchups. How much can you do ?
Which means you CANNOT make a team of three couples to put together twice… Your assignment can only be to make the team of two couples, And B, and only twice… (not three meals.). And having used them in one team , you can’t then use them again, you can’t team A and C together twice. C has to be with someone else twice.
n is the number of couples. So if there are 12 couples, then “1 through n” is “1 through 12”, but if there are 17 couples, then “1 through n” is “1 through 17”.
If this dinner club is to be an on-going thing (and not just for the 12 weeks or whatever and then coming to an end), consider as an extreme alternative the idea of totally randomly assigning your dinner lists; duplication be damned.
This would add an element of unpredictability that would prevent it from becoming boring (not that the no-duplicate-schedule would become boring, probably). Over the longer term, you could expect all combinations of couples to appear in your little parties.
Here’s a schedule that comes close: (I’ll write A,B,C instead of 10,11,12)
1-234
5-678
9-ABC
2-159
3-67A
4-8BC
6-B12
7-94A
8-53C
A-298
B-543
C-167
This solution is defective: 3 doesn’t dine with 9, who also doesn’t dine with 6, who also doesn’t dine with 4. This statement about (3,9,6,4) also applies to (5,A,1,8) and (B,7,2,C).
It’s easy to find solutions where some couples dine with every other couple, but I don’t think you can have every couple dine with every couple with just 12 dinners. In fact, I conjecture you’ll always get some double-misses, as with couples 6,9,1,A,7,2 in the above schedule.
If you’re all still friends after 4 months :o , reassign numbers as follows: Interchange 1 and 6; interchange 2 and 9; interchange 7 and A. Then follow the previous schedule for months 5-8. (The three missing groupings in the quote will meet month 5.)
As others point out, various factors will interfere with the schedule: family emergencies; Mr. A is allergic to Mrs. 6’s Indonesian cooking; Mrs. 2 hates the way Mrs. B flirts with her husband.
4C12 is 495. In other words, there are 495 distinct dinner combos available. Your friends are doing just 12 of them total. To be sure, they’re only aiming for each couple to dine with as many others as possible. Not trying to achieve every possible combination of diners.
But 12 is a heck of a lot less than 495. Like just 2% for round numbers. So it’s not surprising we’re not going to come very close to the ideal of 11 distinct partners per couple over just 4 meals each.
Suppose that there exists a schedule such that every couple dines with every other couple exactly once. Since the couples dine in groups of 4, at each dinner, a given couple dines with three of the other couples. Since they dine with each couple exactly once, the number of other couples must be a multiple of 3. 11 isn’t a multiple of 3, which is a contradiction.
The mathematical name for such a scheduling is a Resolvable Balanced Incomplete Block Design, with blocksize 4.
What does the comparison of 12 with 4C12 have to do with anything, though? As you say, they’re not trying to achieve every possible combination of diners…
septimus had already realized the argument you spell out, and instead considering the question of whether it’s possible to have each couple dine with 10 other couples once and 1 other couple twice.
For example, suppose there were 25 couples, eating dinner in groups of 5, over 6 months. Then perfection could be achieved (exercise left to reader, in case anyone would find it fun), even though the number of possible dinners would be 53,130 while the number of dinners happening would be a mere 30. The ratio would be less than 0.1% (much worse than 2%!), yet all the same, it could be done.
And examples of this sort can be constructed with further arbitrarily low ratios. So I don’t see its relevance.
(I should clarify that the “perfection” of my previous post does not take into account the idea of each couple hosting one particular dinner, just the idea of each couple dining with each other couple precisely once.)
Wait a minute. When you say “495 combinations,” that’s 495 seating combinations, where couple A hosting B (seated across from them), C (seated to right of hosts) & D (seated to left) would be a unique combination; however, in terms of people meeting, those things are not relevant. It’s not even necessary that every couple host everyone once (it’s not even necessary that everyone host the exact same number of times, if someone has volunteered to host an extra time, or, if, because of a number of scheduling conflicts, there’s one dinner with six couples where everyone goes Dutch).
It’s an interesting math problem, but it’s also a real-world situation. Some people are going to have a lot of scheduling conflicts, and there may end up being some 3-couple dinners. There may be a 5-couple dinner, and the host will have to OK that, or everyone will agree to go to Olive Garden on coupon night that evening, or something, instead of the usual 3-star places (or whatever-- for all I know they are going to Taco Bell). They need a survey: Are you OK hosting an extra night, or a 5-couple dinner? Are you OK attending a 3-couple dinner, if conflicts prevent 4 couples attending one month? Are you OK with down-scaling the restaurant one night if someone else hosts an extra dinner? Are you OK with double duplication? There’s probably already a survey regarding dietary needs-- ie, will certain types of restaurants make it hard for you to find choices that fit with your diet (Italian for those with celiac disease, seafood for those with shellfish allergies, Indian for those sensitive to hot food, etc.) A few more questions about hosting and attending that will help the scheduler can’t hurt, and will minimize disappointments.
No, LSLGuy wasn’t counting different seating arrangements as distinct; 495 is just the number of ways to pick 4 couples to eat together out of 12 couples total.
And screw real world scheduling details! My advice to the OP is to get four more couples, go one month longer correspondingly, and achieve perfection (apart from hosting)!