[Math] Combinatorics – group rotation

combinatorics

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.

Best Answer

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.

Related Solutions

[Math] Networking event rotation

It is not hard to show that with $36$ people seated at six tables of six places each, there's no way to reseat everybody to a different table each time without pairing some of the same folks a second time. Consider the six people at the first table during the first seating. Where will they go for their second seating? If they must all go to different tables, one of them would have to remain at that first table (pigeonhole principle).

One idea I'm willing to propose involves $35$ people seated at seven tables of five places each. In this scheme we could have (up to) six rotated seatings, with no pair of people meeting more than once, and no person seated at the same table more than once. I note, however, that your preference was to have an even number ($4$ or $6$) of people at each table. What do you think about the proposed type of scheme?

28 People (Seven Tables of Four Each, Three Rounds without Repeats)

Given the desirability of an even number of people at tables (so that games which require a pair of teammates are conducted), I looked for a solution with seven tables and four people at each table (per round). Here's what I found:

First Round

Table 1:  A1,B1,C1,D1
Table 2:  A2,B2,C2,D2
Table 3:  A3,B3,C3,D3
Table 4:  A4,B4,C4,D4
Table 5:  A5,B5,C5,D5
Table 6:  A6,B6,C6,D6
Table 7:  A7,B7,C7,D7

Second Round

Table 1:  A2,B3,C4,D5
Table 2:  A3,B4,C5,D6
Table 3:  A4,B5,C6,D7
Table 4:  A5,B6,C7,D1
Table 5:  A6,B7,C1,D2
Table 6:  A7,B1,C2,D3
Table 7:  A1,B2,C3,D4

Third Round

Table 1:  A3,B5,C7,D2
Table 2:  A4,B6,C1,D3
Table 3:  A5,B7,C2,D4
Table 4:  A6,B1,C3,D5
Table 5:  A7,B2,C4,D6
Table 6:  A1,B3,C5,D7
Table 7:  A2,B4,C6,D1

It is fairly easy to verify that all twenty-eight people are seated in each round, and that the three seatings at each table are free of repeats. Less easy to spot is whether there are any pairs of people who meet more than once. The design is based on a rotation of a certain kind, so that it actually suffices to check any one person (for duplicate meetings) to be sure that no one meets the same person twice. Here are the seatings for A1 (and you can see there are no repetitions):

Round 1:   A1,B1,C1,D1   (Table 1)
Round 2:   A1,B2,C3,D4   (Table 7)
Round 3:   A1,B3,C5,D7   (Table 6)

It follows that each participant will meet nine other people during this networking event.

Combinatorics – multi-group question – Choose 6 people out of 14, respecting conditions.

A nice way to do this is to use the principle of inclusion-exclusion. Take all $\binom{14}6$ ways to choose $6$ people, then for each country, subtract the assignments where that country has no chosen representatives. The result is $$ \binom {14}6 -\underbrace{\binom{12}6}_{\text{Columbia missing}} -\underbrace{\binom{11}6}_{\text{Chile missing}} -\underbrace{\binom{10}6}_{\text{Argentina missing}} -\underbrace{\binom{9}6}_{\text{Brazil missing}} $$ However, there is a problem. Arrangements with two missing countries will be subtracted twice in the above computation. To fix this, we must add these doubly-subtracted arrangements back in. To the above, we add $$ +\underbrace{\binom{9}{6}}_{\text{Columbia + Chile}} +\underbrace{\binom{8}{6}}_{\text{Columbia + Argentina}} +\underbrace{\binom{7}{6}}_{\text{Columbia + Brazil}} +\underbrace{\binom{7}{6}}_{\text{Chile + Argentina}} +\underbrace{\binom{6}{6}}_{\text{Chile + Brazil}} $$ At this point, we are done! We would not be done if there were any arrangements counted by $\binom{14}6$ with three countries missing, but that is not possible.

Best Answer

Related Solutions

[Math] Networking event rotation

Combinatorics – multi-group question – Choose 6 people out of 14, respecting conditions.

Related Question