Dinner Club Scheduling Challenge

It's been 40 years since engineering school, so I could use some help.
We have a subdivision dinner club. Each year, a leader sets up the schedule.
Knowns:
Number of couples, usually around 16
Number of dinners attended each season, 4
Number of couples per home, usually 4 including the host couple
Each couple hosts once per season

Challenge:
How to schedule couples so that each couple hosts once, and there's an absolute minimum number of times couples attend with the same couples. We don't want couples attending with the same people each time.

 Blog Entries: 8 Recognitions: Gold Member Science Advisor Staff Emeritus Hmm, that's a problem in discrete math called designs. I'll think about it tomorrow if nobody else posts. I'm not good in discrete math, though Some design problems are notoriously hard though. Kirkman's problem is an example of a really hard similar problem.

Blog Entries: 8
Recognitions:
Gold Member
Staff Emeritus

Dinner Club Scheduling Challenge

OK, I did it now anyway. Here is a near-optimal solution. (the hosts are bolded)

1 5 9 13
2 5 12 15
3 5 10 16
4 6 9 15
4 5 11 14
3 6 12 16
2 7 9 16
1 8 10 15
3 8 9 14
4 7 10 13
2 8 11 13
1 7 12 14
4 8 12 13
2 6 10 14
3 7 11 15
1 6 11 16

For people curious on how I obtained this. I noticed that $16=4^2$. So I started looking to lines in 2-dimension $\mathbb{F}_4$-space. Using GAP ( http://www.gap-system.org/gap.html ) and the DESIGN-package ( http://designtheory.org/software/gap_design/ ) I found an optimal solution.

However, the solution implied each couple having to go to 5 dinners. This was easily solved by eliminating 4 dinners, and I still had an optimal solution. However, each couple has to host once. This I couldn't satisfy, so I changed 2 numbers in the design. This no longer makes it optimal, but it's very close.

 It certainly seems you've solved the problem! Just brilliant...... I tried a simple 2 dimensional matrix and quickly saw that fail. I'm impressed (not that I'm surprised to be). I'll need to dive into your approach to see if I can duplicate it myself as the number of caveats and/or as conditions change... ie, number of couples. Thank you so much!
 I spent more time reviewing the solution and see a problem. Maybe it has to do with how to use the result. If I look at the first four rows as being the first dinner session, couple #5 attends with three hosts. They should be assigned to only one row(host).

Blog Entries: 8
Recognitions:
Gold Member
Staff Emeritus
 Quote by Greg'sDad I spent more time reviewing the solution and see a problem. Maybe it has to do with how to use the result. If I look at the first four rows as being the first dinner session, couple #5 attends with three hosts. They should be assigned to only one row(host).
Oh, so you want the dinner parties to happen at the same time?? Yes, I can see how you want that, and I certainly didn't think of that constraint.

This makes the problem a little more difficult. I'll have to think about the solution.

 It was careless for me not to mention that.... Apologies. By the way, the next planning session won't happen until next summer, so don't feel rushed.... Thanks again.
 Blog Entries: 8 Recognitions: Gold Member Science Advisor Staff Emeritus What about this: (1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 16) (1 5 9 13) (2 6 10 14) (3 7 11 15) (4 8 12 16) (1 6 11 16) (2 7 12 13) (3 8 9 14) (4 5 10 15) (1 7 12 14) (2 8 9 15) (3 5 11 13) (4 6 10 16) This solution is not optimal (as an optimal solution can not exist). So here are the couples who have to sit twice with eachother: 3 11 4 10 4 16 5 13 6 10 6 16 7 12 8 9 Be sure that 4 6 10 and 16 like eachother. I'll look for a more optimal solution.
 It's really an interesting problem. I'd make a small change to start with: (1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 16) (1 5 9 13) (2 6 10 14) (3 7 11 15) (4 8 12 16) (1 6 11 16) (2 7 12 13) (3 8 9 14) (4 5 10 15) (1 7 12 14) (2 8 9 15) (3 5 11 13) (4 6 10 16)
 Blog Entries: 8 Recognitions: Gold Member Science Advisor Staff Emeritus Oh sorry, I meant to change that in a 10, I think... There is no way you can make a solution where nobody meets eachother more than once (this would be the optimal solution). But now you have some people meeting one couple twice and some people meeting two couples twice. A nice mathematical problem is whether you can make a solution where every couple only meets one other couple twice. I think such a thing is impossible, but I'm not sure why. In any case, it's an immensely interesting problem, thanks for asking!!
 My first try: ( 1 2 3 4) ( 5 6 7 8) ( 9 10 11 12) (13 14 15 16) ( 1 5 9 13) ( 2 6 10 14) ( 3 7 11 15) ( 4 8 12 16) ( 1 6 11 16) ( 2 7 12 13) ( 3 8 9 14) ( 4 5 10 15) ( 1 7 9 14) ( 2 8 10 15) ( 3 5 11 16) ( 4 6 12 13) The following 7 couples meet each other twice, with 10, 11 and 12 featuring twice (2 10) (3 11) (4 12) (9 14) (10 15) (11 16) (12 13)
 Don't think I can improve on this at the moment: ( 1 2 3 4) ( 5 6 7 8) ( 14 10 11 12) (13 9 15 16) ( 1 5 10 13) ( 2 6 9 14) ( 3 7 11 15) ( 4 8 12 16) ( 1 6 11 16) ( 2 7 12 13) ( 3 8 9 10) ( 4 5 14 15) ( 1 7 9 14) ( 2 8 10 15) ( 3 5 12 16) ( 4 6 11 13) The following 4 couples meet each other twice: (6 11) (8 10) (9 14) (12 16) Edit: it could obviously be improved by normalising (swap 9 and 14 everywhere): I'll leave that for others...
 I knew there was an optimal solution in there somewhere: (1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 16) (1 5 9 13) (2 6 10 14) (3 7 11 15) (4 8 12 16) (1 6 11 16) (2 5 12 15) (3 8 9 14) (4 7 10 13) (1 7 12 14) (2 8 11 13) (3 5 10 16) (4 6 9 15) No couple meets twice.

Blog Entries: 8
Recognitions:
Gold Member