4
$\begingroup$

I’m an elementary grade teacher and I want to organize a speed meeting event at the start of the school year to introduce the new staff. Specifically, I want to organize 3-minute rounds during which trios of teachers would chat. Trios would then be split and reorganized for another round and so on. The idea is to organize the trios and the round so that any pair of teachers cannot be in the same trio more than once. In other words, if Arlene gets matched with Bob and Carlito in round 1, she could no longer be match with any of those two. She could still be matched with Denise, Farley or any other teacher.

In order for such a pairing system to work, there must be an odd number of attendees that is divisible by 3 (so 3, 9 or 15 people should do). Otherwise, there would either be some tables with less than 3 persons or some people left in pairs for the last round. Through trial and error, I was able to find two working configuration of pairings for a 9-persons meeting:

1st round: ABC DEF GHI

2nd round: ADG BEI CFH

3rd round: AEH BFG CDI

4th round: AFI BDH CEG

Things get way more complicated with 15 or 21 attendees (the latter being the target I have in mind for the event to be held in a couple of weeks). My wife and I tried to code something in R to find a working configuration, but we couldn’t beat this puzzle. Is anybody able to help me on that one? Can anybody point me to an algorithm (or to a solution!)?

Best regards,

$\endgroup$
4
$\begingroup$

This is known as the social golfer problem. A number of questions on site discuss it.

A famous groups-of-3 version is Kirkman's schoolgirl problem -- which is essentially your 15 teacher question. These sorts of problems are intimately related to balanced incomplete block designs in statistics (solutions to a number of social golfer problems are BIBDs). The issue is essentially one of finding largest-possible sets of mutually orthogonal Latin rectangles (MOLRs).

Ones where everybody meets absolutely everybody else would be the fully social golfer problem.

The longest 15 18 and 21 golfer matchups I know of are 7, 8 and 10 rounds -- and I think those will be the longest possible without re-meeting anyone. The 15 and 21 golfer versions should be fully social:

15 golfers, threesomes, 7 rounds
ABC DEF GHI JKL MNO
ADG BEJ CFM HKN ILO
AEN BDO CHL FIK GJM
AIM BGL CDK EHO FJN
AHJ BKM CEI DLN FGO
AFL BIN CJO DHM EGK
AKO BFH CGN DIJ ELM 

18 golfers, threesomes, 8 rounds
ABC DEF GHI ahf dbi gec
Abc Def Ghi aHF dBI gEC
abC deF ghI AHf DBi GEc
aBc dEf gHi AhF DbI GeC
ADG BEH CFI aei bfg cdh
Adg Beh Cfi aEI bFG cDH
adG beH cfI AEi BFg CDh
aDg bEh cFi AeI BfG CdH

21 golfers, threesomes, 10 rounds
ABF EGM DKR INP CJT HOU LQS
DEJ HIK BNO AQR CLU FMS GPT
AHL JKO EIQ CNR BGS DMT FPU
BCD FHN ELP GOQ AKT IMU JRS
EFK IGL COM BRP AJU DNS HQT
BIJ KLM FGR AOP CHS ENT DQU
CAE DIO FJQ HMR BLT GNU KPS
FDL GHJ AMN CPQ BKU EOS IRT
CGK LJN DHP BMQ AIS FOT ERU
STU ADG BEH CFI JMP KNQ LOR

(These are in very old files I had ... saved from computer to computer over many years. It's possible I might have generated all of these myself -- I solved quite a few of these by hand -- or I may have taken them from one of a number of webpages or other sources in the 2000s, but if it's the latter I can't seem to locate the sources now to give credit; I am pretty sure that the one with lower case letters in it will almost certainly be one I made myself, though. I'll happily offer credit on any of these if I can find where they came from. I played with this problem quite a bit in the mid to late 1990s and some more in the early 2000s in the process of making a scheduler for boardgame tournaments - mostly for games which had 3 or 4 players, but I had some results for games with more players per table as well.)

There were once an extensive set of web pages (done by Warwick Harvey) with a collection of the best known solutions available but they disappeared long ago.

[Edit: See the wayback machine here, but to my recollection there were better solutions to many of those before the pages disappeared (a couple of years after that snapshot, I think).]

There are better (i.e. longer) solutions to quite a few of the problems at Ed Pegg Jr's Math Games pages Social Golfer problem, but Warwick's pages above are more extensive (give solutions for problems not covered here); it's a shame the more up to date results are gone.

If you can get hold of it, the CRC Handbook of Combinatorial Designs has quite a bit of information on this problem.

There's also a connection between MOLS and orthogonal arrays, so places that list orthogonal arrays (like Neil Sloane's library can be a way to find solutions.

Further hardmath mentions in comments that there's the La Jolla Covering Repository D. Gordon's new location for the covering repository where a large number of solutions are searchable.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Re "the longest": the OP notes there must be $n=6k+3$ people in the "fully social" problem. Since any individual will meet two new people in each round, the maximum number of rounds is $(n-1)/2=(6k+3-1)/2 = 3k+1$. For $n=15,21$ those values are $7$ and $10$, respectively. Similar reasoning shows the maximum for $n=18$ is $8$ (but each person will not meet some other person). $\endgroup$ – whuber Jul 29 '17 at 14:05
  • $\begingroup$ Thanks for this useful answer. Everything is clear. I'm happy to hear this problem actually had a name and was more than a century old. $\endgroup$ – Jérémie Jul 29 '17 at 23:34
  • $\begingroup$ @Jérémie There's also a connection to Euler's 36 officer problem, which demonstrates that for meetings between 36 golfers in groups of 6, you can't get any more than three rounds before at least a pair of players is playing with someone they already met (i.e. on the fourth round, there's at least one pair repeating an earlier meeting) $\endgroup$ – Glen_b Jul 30 '17 at 1:21
  • $\begingroup$ Dan Gordon migrated the La Jolla covering design repository to his new site, so it might be a good idea to update your link. $\endgroup$ – hardmath Mar 16 at 1:50
2
$\begingroup$

Here's a simple-minded approach in Python that assigns people at random for each round. The program runs this logic (the tryit function) n_attempts times and prints out a configuration with the largest observed number of rounds. You can set the people list manually to output names rather than numbers.

from random import sample
from itertools import combinations

people = list(range(21))
group_size = 3
n_attempts = 1000

def tryit():
    rounds = [[]]
    seen = set()
    for i in range(0, len(people), group_size):
        rounds[0].append(people[i : i + group_size])
        seen.update(combinations(rounds[0][-1], 2))
    while True:
        r = [[] for _ in range(len(people) // group_size)]
        def f(p):
            for group in sample(r, len(r)):
                if len(group) < group_size:
                    pairs = [tuple(sorted((p, p2))) for p2 in group]
                    if seen.isdisjoint(pairs):
                        group.append(p)
                        seen.update(pairs)
                        return True
            return False
        for p in people:
            if not f(p):
                return rounds
        rounds.append(r)

rounds = max((tryit() for _ in range(n_attempts)), key = len)

for i, r in enumerate(sorted(sorted(r) for r in rounds)):
    print("Round {}: {}".format(i + 1, r))

For example, with 21 people, I get:

Round 1: [[0, 1, 2], [3, 4, 5], [6, 7, 8], [9, 10, 11], [12, 13, 14], [15, 16, 17], [18, 19, 20]]
Round 2: [[0, 3, 7], [1, 5, 11], [2, 13, 17], [4, 8, 10], [6, 16, 18], [9, 12, 20], [14, 15, 19]]
Round 3: [[0, 5, 15], [1, 6, 9], [2, 3, 20], [4, 14, 18], [7, 16, 19], [8, 11, 13], [10, 12, 17]]
Round 4: [[0, 8, 17], [1, 14, 16], [2, 15, 18], [3, 11, 12], [4, 7, 20], [5, 6, 10], [9, 13, 19]]
Round 5: [[0, 9, 18], [1, 7, 15], [2, 10, 16], [3, 6, 13], [4, 11, 17], [5, 12, 19], [8, 14, 20]]
Round 6: [[0, 11, 16], [1, 10, 19], [2, 5, 14], [3, 8, 9], [4, 13, 15], [6, 17, 20], [7, 12, 18]]
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very useful program $\endgroup$ – Graham G Nov 18 at 12:41

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.