8
$\begingroup$

I wrote an article on the Social Golfer Problem, which has questions like:

Each day, 16 people play Munchkin in foursomes simultaneously. How many days can they play with no two people playing with each other twice? tournament

I compiled best-known solutions for pairs, triplets, and quadruplets at the Social Golfer Problem Demonstration. To compile this data, I had to read through a few hundred books and papers. Very often, an answer would be given in new-to-me difficult notation, or it would reference a previous paper, or it would just be "obvious".

Now that I am considered an "expert", I've been asked about quintets and sextets, and for larger number of groups. I don't recall seeing solutions for any of the below problems in the papers I perused, but it's possible I missed them.

  • 30 play in groups of 3 each day. No two play together more than once. How many days?
  • 33 play in groups of 3 each day. No two play together more than once. How many days?
  • 36 play in groups of 3 each day. No two play together more than once. How many days?
  • 40 play in groups of 4 each day. No two play together more than once. How many days?
  • 44 play in groups of 4 each day. No two play together more than once. How many days?
  • 48 play in groups of 4 each day. No two play together more than once. How many days?
  • 52 play in groups of 4 each day. No two play together more than once. How many days?
  • 25 play in groups of 5 each day. No two play together more than once. How many days?
  • 30 play in groups of 5 each day. No two play together more than once. How many days?
  • 35 play in groups of 5 each day. No two play together more than once. How many days?
  • 40 play in groups of 5 each day. No two play together more than once. How many days?
  • 45 play in groups of 5 each day. No two play together more than once. How many days?
  • 50 play in groups of 5 each day. No two play together more than once. How many days?
  • 55 play in groups of 5 each day. No two play together more than once. How many days?
  • 60 play in groups of 5 each day. No two play together more than once. How many days?
  • 36 play in groups of 6 each day. No two play together more than once. How many days?
  • 42 play in groups of 6 each day. No two play together more than once. How many days?
  • 48 play in groups of 6 each day. No two play together more than once. How many days?
  • 54 play in groups of 6 each day. No two play together more than once. How many days?
  • 60 play in groups of 6 each day. No two play together more than once. How many days?
  • 66 play in groups of 6 each day. No two play together more than once. How many days?
  • 72 play in groups of 6 each day. No two play together more than once. How many days?

Does anyone have any solutions to any of these?

$\endgroup$
3
  • 3
    $\begingroup$ 25 players in groups of five is easy. There are six possible directions for a line in the plane $F_5^2$ over the field of five elements. Thus the points of the plane can be partitioned to five lines (five points on each) in six ways. Using that idea we can see do the groups in such a way that after 30 days each player has played in 6 groups, and exactly once with all the other 24 players. The uniqueness comes from the fact that two points (=two players) determine a unique line. $\endgroup$ Oct 2 '11 at 20:10
  • 2
    $\begingroup$ Oops. I meant that you can arrange 30 parties of five players. If each player will play every day that is only good for 6 days. Five groups playing on each day. $\endgroup$ Oct 2 '11 at 20:13
  • 2
    $\begingroup$ demonstrations.wolfram.com/SocialGolferProblem is very cool! But it lists solutions only for (n golfers, g groups of m) where m < g. I'm interested in solutions for (n golfers, g groups of m) where m >> g. For example, "35 play in 5 groups of 7 each day. No two play together more than once. How many days?" or "98 play in 7 groups of 14 each day. No two play together more than once. How many days?" Any leads on that kind of problem? math.stackexchange.com/questions/3195281/… $\endgroup$ May 4 '19 at 16:58
3
$\begingroup$

Have you seen Ivan Dotu and Pascal Van Hentenryck, Scheduling social golfers locally? They claim

45 golfers in groups of 5 can play 7 days;

54 golfers in groups of 6 can play 6 days;

50 golfers in groups of 5 can play 8 days;

and some other results that lie outside the bounds of your question. But they don't actually present any instances of the solutions, just their algorithm and the amount of time it took to find the instances.

$\endgroup$
1
  • $\begingroup$ Yes, that's one of the less helpful papers I looked at. $\endgroup$
    – Ed Pegg
    May 11 '15 at 15:36
2
$\begingroup$

I don't have a lot of advice on quintets in particular, but perhaps the information below will be useful nevertheless.

Some of the solutions you are looking for correspond to the necessary conditions for a resolvable balanced incomplete block designs and, if such a RBIBD exists, then this will lead immediately to a solution with the maximal number of days. The items in this category are:

  • 33 play in groups of 3 for 16 days - the much studied Kirkman Triple System
  • 40 play in groups of 4 for 13 days - see Kageyama (1972)
  • 52 play in groups of 4 for 17 days - see Lam & Miao (1999) Lemma 5.3
  • 25 play in groups of 5 for 6 days - see comment above
  • 45 play in groups of 5 for <=11 days - RBIBD is an open problem
  • 36 play in groups of 6 for <7 days - RBIBD does not exist
  • 66 play in groups of 6 for <=13 days - RBIBD is an open problem

In addition to the above, I can offer examples of the following:

  • 30 play in groups of 3 for 14 days [maximal]
  • 36 play in groups of 3 for 17 days [maximal]
  • 44 play in groups of 4 for 13 days
  • 48 play in groups of 4 for 14 days [see Ge and Lam(2003) Lemma 3.1]
  • 45 play in groups of 5 for 9 days.

I have also been confused by the large literature on this subject. I feel that 44/4/14 days, and 48/4/15 days should both be possible, but I have not come across a construction yet.

References:

Ge & Lam (2003) "Resolvable group divisible designs with block size four and group size six"; Discrete Mathematics, 268, 139 – 151.

Kageyama (1972) "A survey of resolvable solutions of balanced incomplete block designs"; Rev. Inst. Internat. Statist., 40, 269–273.

Lam & Miao (1999) "On Cyclically Resolvable Cyclic Steiner 2-Designs", Journal of Combinatorial Theory, Series A 85, 194-207.

$\endgroup$
2
$\begingroup$

The Social Golfer Problem with triples and an odd number of groups is studied using Kirkman Triple Systems. This page claims that $6n+3$ golfers playing in triplets can play for $3n+1$ days (for all nonnegative $n$). This is proven in the following paper (though I haven't checked this myself).

EDIT:

I did some more research. If $6n \ge 18$ players are playing in triplets, they can play for $3n-1$ days. This follows from the study of Nearly Kirkman Triple Systems. The proof is spread out over multiple papers, the following paper cites them:

Furthermore, if $12n+4$ players play in groups of 4, they can play for $4n+1$ days. This is proven in

Furthermore, Asymptotic Existence of Nearly Kirkman Systems, Hao Chen, Wen-Song Chu makes the following claims (citing other papers for the first two claims and proving the third)

  • If $12n\ge24$ players play in groups of 4, they can play for $4n-1$ days, except possibly for $12n\in\{84, 132, 264, 372, 456, 552, 660, 804, 852\}$.
  • For a fixed group size $k$ for all but finitely many $n \equiv k \mod k(k-1)$ we have that $n$ golfers can play the optimal $\frac{n-1}{k-1}$ number of days.
  • For a fixed group size $k$ for all but finitely many $n \equiv 0 \mod k(k-1)$ we have that $n$ golfers can play the optimal $\frac{n}{k-1}-1$ number of days.

This answers the following questions:

  • 30 play in groups of 3 for 14 days.
  • 33 play in groups of 3 for 16 days.
  • 36 play in groups of 3 for 17 days.
  • 40 play in groups of 4 for 13 days.
  • 48 play in groups of 4 for 15 days.
  • 52 play in groups of 4 for 17 days.
$\endgroup$
2
$\begingroup$

A new (Dec 2020) paper on this topic uses symmetry to approach the problem, and publishes solutions for groups up to 50 participants: Breakout Group Allocation Schedules and the Social Golfer Problem with Adjacent Group Sizes

$\endgroup$

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.