I’m interested in the following problem. There is a group of 42 people. Each night for four nights they will have dinner in 6 groups of 7. What algorithm do I use to maximize the number of people that each person will have dinner with. Certainly this type of problem has a name and has probably been solved.
I don’t know of a name, but I do know of a solution (one of many tied for most optimal). Put the 42 people in a grid of 6 columns and 7 rows. The first night, each column is one dinner group. The second night, shift the second row over to the right by one space, the third row over two spaces, the fourth row over three spaces, and so on, wrapping around to the left for anyone who leaves the grid. The third night, shift them again in the same way, and then again on the fourth night (equivalently, you can take diagonal stripes through the grid instead of shifting the rows). If I’m not mistaken, this should have every person end up dining with 24 other folks, with no repeats.
Chronos, thanks as always. Using your basic idea, I’ve got a grouping that will work for 7 groups of 6 people each for dinner rather than 6 groups of 7 (probably better in any case since a reservation for 6 is probably much easier than a reservation for 7).
But I don’t think your method works for 6 groups of 7. In fact I believe that problem can’t be done with maximum meeting after more thought. The first night each column is obviously fine. On the second night for man 1 I can only take one person from each other column (otherwise if I take two from any column they will have had dinner together on night one), but there are only 5 other columns (excluding the first) so I can only pick 5 additional people so I can’t get 7 into the group.
I also wonder if your method works when the number of people in a group is even. After I do a number of shifts equal to half the column size, I’ll cycle rather than pick the others. I think I need to use a shift size that that is relatively prime with the number in each group.
Another thought. Under the suggested algorithm, each person will never have dinner with anyone else in his original row, so when the number of nights increases, to what might give a solution with each person having dinner with everyone else exactly once, this algorithm won’t be able to find it.
Call the number of groups G, the number of people in a group P, and the number of nights N.
Chronos’s solution (label the people by ordered pairs (g, p) where g < G and p < P, and on night n, have all the people (g + n * i mod G, i) for i < P dine together) should work (in the sense of no repeat pairings) precisely whenever G cannot be factored into a product of two numbers, one less than P and the other less than N.
So, in particular, with G = 7, P = 6, and N = 4, this works, but with G = 6, P = 7, and N = 4, this does not work.
Do you require that each person meets the same number of people? That might not be possible in general. Instead, you might try to maximize the minimum number of people that any person meets.
I was actually going for the latter – maximize the minimum number of meets. But I’d think usually the best answer would always be each person meets m or m-1 others. That is, if the total number of people is not a multiple of the size of a dinner group, you’d always get the right answer by adding the smallest number imaginary people until the total was a multiple of the group size, solving that problem, and then tossing out the “imaginaries” so some dinner groups were one smaller.
Hm, yes, my solution is flawed. My hunch is still that there should exist some perfect solution, though (at least with this relatively small number of nights). I’ll have think about this some more.
Not necessarily. The “imaginary people” might end up grouped together, in which case, instead of having a number of groups smaller by 1, you might have a single group that’s significantly smaller.