In discrete mathematics, the social golfer problem (SGP) is a combinatorial-design problem derived from a question posted in the usenet newsgroup sci.op-research in May 1998.^[1] The problem is as follows: 32 golfers play golf once a week in groups of 4. Schedule these golfers to play for as many weeks as possible without any two golfers playing together in a group more than once.

More generally, this problem can be defined for any ${\displaystyle n=g\times s}$ golfers who play in ${\displaystyle g}$ groups of ${\displaystyle s}$ golfers for ${\displaystyle w}$ weeks. The solution involves either affirming or denying the existence of a schedule and, if such a schedule exists, determining the number of unique schedules and constructing them.

Challenges

Permutations that lead to isomorphic solutions to the social golfer problem.

The SGP is a challenging problem to solve for two main reasons:^[2]

First is the large search space resulting from the combinatorial and highly symmetrical nature of the problem. There are a total of ${\displaystyle (n!)^{w}}$ schedules in the search space. For each schedule, the weeks ${\displaystyle (w!)}$, groups within each week ${\displaystyle (g!)}$, players within each group ${\displaystyle (s!)}$, and individual player ${\displaystyle (n!)}$ can all be permuted. This leads to a total of ${\displaystyle w!\times g!\times s!\times n!}$ isomorphisms, schedules that are identical through any of these symmetry operations. Due to its high symmetry, the SGP is commonly used as a standard benchmark in symmetry breaking in constraint programming (symmetry-breaking constraints).

Second is the choice of variables. The SGP can be seen as an optimization problem to maximize the number of weeks in the schedule. Hence, incorrectly defined initial points and other variables in the model can lead the process to an area in the search space with no solution.

Solutions

The SGP is the Steiner system S(2,4,32) because 32 golfers are divided into groups of 4 and both the group and week assignments of any 2 golfers can be uniquely identified. Soon after the problem was proposed in 1998, a solution for 9 weeks was found and the existence of a solution for 11 weeks was proven to be impossible. In the case of the latter, note that each player must play with 3 unique players each week. For a schedule lasting 11 weeks, a player will be grouped with a total of ${\displaystyle 3\times 11=33}$ other players. Since there are only 31 other players in the group, this is not possible.^[3] A solution for 10 weeks could be obtained from results already published in 1996.^[4] It was independently rediscovered using a different method in 2004,^[5] which is the solution presented below.

There are many approaches to solving the SGP, namely design theory techniques,^[6][7] SAT formulations (propositional satisfiability problem), constraint-based approaches,^[8] metaheuristic methods, and radix approach.

The radix approach assigns golfers into groups based on the addition of numbers in base ${\displaystyle k}$.^[9] Variables in the general case of the SGP can be redefined as ${\displaystyle n=s^{k}}$ golfers who play in ${\displaystyle g=s^{k-1}}$ groups of ${\displaystyle s}$ golfers for any number ${\displaystyle k}$. The maximum number of weeks that these golfers can play without regrouping any two golfers is ${\displaystyle (k^{n}-1)/(k-1)}$.

Applications

Working in groups is encouraged in classrooms because it fosters active learning and development of critical-thinking and communication skills. The SGP has been used to assign students into groups in undergraduate chemistry classes^[9] and breakout rooms in online meeting software^[10] to maximize student interaction and socialization.

The SGP has also been used as a model to study tournament scheduling.^[11]

See also

• Steiner system
• Kirkman's schoolgirl problem
• Euler's officer problem
• Round-robin tournament

References

External links

• Wolfram Community: Radix Approach to Solving the Social Golfer Problem and Graph Visualization
• Wolfram Mathworld: Social Golfer Problem