4
$\begingroup$

Anyone able to provide me with a solution to this problem?

I came across this website whilst struggling with the following problem. Whilst I have found and read bits that have helped, I still can't solve this particular situation. I'm not a mathematician in any sense of the word so really would appreciate some help.

I have 5 groups of people. 4 of the groups have 4 people and the other one has 2 people - so 18 people in total. I have to come up with a system to allow each of the people in each group to meet each other. The meetings need to be in groups of 3-4. Some quick and basic maths suggested to me to have 6 meetings of 3 people for 6 weeks. I just can't come up with the right algorithm to get this organised. I have literally spent hours on it and got no where.

What I tried most recently was:

Wk 1:   Mtg 1    Mtg 2    Mtg 3    Mtg 4    Mtg 5    Mtg 6
        GATL1    GATL2    GATL3    GATL4    GBTL1    GBTL2
        GCTL4    GCTL3    GCTL2    GCTL1    GBTL4    GBTL3
        GDTL1    GDTL2    GDTL3    GDTL4    GETL1    GETL2

Wk 2:   Mtg 1    Mtg 2    Mtg 3    Mtg 4    Mtg 5    Mtg 6
        GETL2    GATL1    GATL2    GATL3    GATL4    GBTL1
        GCTL3    GCTL2    GCTL1    GBTL4    GBTL3    GBTL2
        GCTL4    GDTL1    GDTL2    GDTL3    GDTL4    GETL1

etc. etc. for 6 weeks. The only problem is that this didn't ensure that everybody met with everybody else.

Very grateful for your assistance.

$\endgroup$
  • $\begingroup$ So Group E has 2 people. Each of these two has to meet 16 other people. In your partial schedule, each one meets only 2 new people a week. At that rate, it will take 8 weeks (at least!), not 6. So you had better have a lot of your meetings involve 4 people, not 3. $\endgroup$ – Gerry Myerson Jul 30 '13 at 8:49
  • $\begingroup$ What are those letters/numbers indicating? The identity of the persons attending a meeting surely, but how to decipher that? Person G surely doesn't attend all the meetings? $\endgroup$ – Jyrki Lahtonen Jul 30 '13 at 8:54
  • 2
    $\begingroup$ @AlexanderGruber Perhaps some clarification of your recommendation to ask on meta is needed here. $\endgroup$ – Martin Sleziak Aug 1 '13 at 11:26
  • 1
    $\begingroup$ Okay, so are you saying that each individual must meet with each other individual? Or are you saying that each individual must meet with at least one person from each group? $\endgroup$ – Ataraxia Aug 1 '13 at 13:34
  • 2
    $\begingroup$ And so where do the groups come into play? It sounds to me from what you described groups don't really make any difference, so perhaps I'm missing something? Like, do people need to meet with others within their own group? $\endgroup$ – Ataraxia Aug 1 '13 at 14:54
1
$\begingroup$

This is not a complete answer. I've renamed the people 1 through 18. The five groups are:

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

Here are the meetings in Week 1:

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

Week 2:

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

Week 3:

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

Week 4:

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

Week 5:

1 6 9 ... 2 10 12 ...

Week 6:

1 14 16 ... 2 6 18 ...

I don't know whether one can complete the Week 5 and Week 6 schedules to have everyone meet everyone. I know that 1 and 2 have met everyone, and most of the others have met 10 of the 14 they have to meet. 3 still has to meet 9, 10, 17 and 18; 4 has to meet 11, 13, 16; and so on.

$\endgroup$
  • $\begingroup$ Thanks for your reply and for your kind assistance. I thought there would be a mathematical solution to this problem that would make it all easy. Some kind of pattern that could be applied? Otherwise, if it's a simple case of having to go through and marry people up step-by-step, then that's what I'll do. I just thought that there had to be an easier way? $\endgroup$ – Ady Aug 1 '13 at 14:46
  • 1
    $\begingroup$ The question falls into the general area of "combinatorial designs" (a good keyphrase if you want to do some searching). There are some problems in that area where there are formulas, and there are some where no one knows whether there is a solution until someone exhausts all the possibilities. Maybe your problem falls in the first group and I just don't know it. $\endgroup$ – Gerry Myerson Aug 1 '13 at 23:36
  • 1
    $\begingroup$ Actually, I think your problem can be put into a form that has been studied before. Invent two fictional people to fill out your group of two, so now you have 5 groups of 4. Now you want 7 weeks of meetings, 5 4-person meetings each week, everyone meets everyone; in Week Zero, you just meet the people in your own group. This is something like the "Kirkman schoolgirl problem" with "Steiner triple systems" except you have quadruples instead of triples. If there is a solution, you can then delete the fictional people and Week Zero, and what's left is what you want. $\endgroup$ – Gerry Myerson Aug 2 '13 at 0:28
  • $\begingroup$ I think I agree with Gerry Myerson's last comment. My limited experience with combinatorial designs suggested to me that the last group being smaller made this problem much uglier, and that was a big reason, why I didn't think about it. The two phantom members for group E do make it more symmetric, but even so the numbers don't mesh together very nicely, so it may be difficult to use one of the general solutions for this kind of problems. But may be not? Who knows? +1 to you both. $\endgroup$ – Jyrki Lahtonen Aug 2 '13 at 20:01
  • $\begingroup$ It's sort of dual to the Social Golfer problem. There, you have 20 golfers, and you want to play as many rounds of golf as possible, with the golfers split in 5 groups of 4, no pair of golfers in the same foursome twice. You want to play as few rounds as possible, each pair of golfers in the same foursome at least once. The solution of (this instance of) social golfer is they can play at most 5 rounds, and you can find a solution by websearch. Maybe starting with some such solution, you can tack on another 2 rounds to solve your problem. $\endgroup$ – Gerry Myerson Aug 2 '13 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.