Combinatorial solutions to the Social Golfer Problem and Social Golfer Problem with Adjacent Group Sizes Publication type: Article Volume: 00
Alice Miller, Ivaylo Valkov, R. Julian R. Abel · 2025
Read Combinatorial solutions to the Social Golfer Problem and Social Golfer Problem with Adjacent Group Sizes Publication type: Article Volume: 00 by Alice Miller, Ivaylo Valkov, R. Julian R. Abel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-23376.txt.
Introduction
Alice Miller, Ivaylo Valkov, and R. Julian Abel solve scheduling puzzles with design theory, in a 2025 paper. The Social Golfer Problem asks how to split golfers into weekly groups so no pair repeats across weeks. A variant allows group sizes that sit side by side. The authors build optimal schedules from resolvable designs, balanced block designs, and latin squares and rectangles. A general algorithm finds an optimal solution for any setup. Full solution sets cover fields of up to one hundred fifty players.
Catalog record
| CREATOR | Alice Miller, Ivaylo Valkov, R. Julian R. Abel |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 119 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-23376
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Combinatorial solutions to the Social Golfer Problem and Social Golfer Problem with Adjacent Group Sizes Publication type: Article Volume: 00 Alice Miller, Ivaylo Valkov, R. Julian R. Abel Abstract Resolvable combinatorial designs including Resolvable Balanced Incomplete Block Designs, Resolvable Group Divisible Designs, Uniformly Resolvable Designs and Mutually Orthogonal Latin Squares and Rectangles are used to construct optimal solutions to the Social Golfer problem (SGP) and the Social Golfer problem with adjacent group sizes (SGA). An algorithm is presented to find an optimal solution in general, and a complete set of solutions is provided for up to 150 players. keywords Social Golfer Problem; Allocations; Scheduling; Block Designs; Resolvable; Breakout Room; Small Group Teaching. † † copyright-year: 2023 † † startpage: 1 † † titlemark: Combinatorial solutions to the Social Golfer Problem and Social Golfer Problem with Adjacent Group Sizes † † corresponding: Corresponding author Alice Miller. MILLER et al. \presentaddress This is sample for present address text this is sample for present address text. 1 Introduction The study of combinatorial designs [ 44 , 76 ] is a well-established area of mathematical research. A combinatorial design is an arrangement of a set of elements into defined substructures ( blocks ) in such a way that desired combinatorial properties are satisfied. They have many applications in, for example, communications, cryptography and networking [ 45 ] , optical orthogonal codes [ 50 ] , cancer trial design [ 24 ] and genetic screening algorithms [ 75 ] . In this paper we are mainly interested in designs for which every pair of elements appears in exactly one block together and one of the desirable properties is resolvability , i.e., where the blocks can be arranged into rounds in which every element appears once. Such designs are called resolvable designs [ 56 ] . In recent work [ 95 ] , we highlighted the link between resolvable designs and another mathematical problem: the Social Golfer problem SGP. The Social Golfer problem is to allocate v players into groups of equal size over as many rounds as possible. No two players should play together in more than one round, and the goal is to allocate as many rounds as possible. We note that the terms used in SGP (such as group ) conflict with similar terms used in combinatorial designs. In Section 2 we restate the problem using combinatorial design terminology. We were initially drawn to the problem when trying to allocate participants in large online calls (i.e. on Zoom or Teams) to successive breakout rooms during the COVID-19 pandemic. We soon realised that the allocation problem had more general application in a teaching context (when allocating students to successive study groups for example). Allocating as many rounds of groups as possible, whilst ensuring that no two students appear in the same group together more than once directly maps to the Social Golfer problem. Indeed these allocations are examples of a class of combinatorial designs known as resolvable maximum packings [ 59 , 118 ] . In [ 95 ] we also considered the case where there are two group sizes which differ by one, and in each round the number of groups of each size is constant. We called this the Social Golfer problem with adjacent group sizes (SGA). This is very helpful in situations where the total number of participants does not have any suitable divisors. We provided an initial list of the best solutions we could find for (student) class sizes of up to 50 and group sizes either a divisor of the class size or a pair of consecutive values in \{(4,5),(5,6)\} . In most cases we found our solutions by adapting resolvable designs, in particular resolvable balanced incomplete block designs and a particular type of resolvable group divisible design , namely resolvable transversal designs . In some cases we used (or adapted) existing published best solutions for the SGP. We also made all our solutions available on our web application BoRAT, the link for which can be found at [ 94 ] . We continue to add solutions as they are generated. In this paper we re-introduce the SGP and the SGA, and present examples of the combinatorial designs that we use to find good solutions to them. We both improve on solutions given in [ 95 ] and extend our results to up to 150 participants. We also give complete solutions for the SGP with group sizes 3 or 4 for any (suitable) number of participants. We explain the methods used in [ 95 ] and introduce additional methods based on other resolvable, or partially resolvable designs such as resolvable group divisible designs , uniformally resolvable designs and incomplete resolvable transversal designs . We describe some of the constructions used and highlight some difficult cases - presenting the best current solution to solve them. We present an algorithm to determine which method to use to find an optimal solution when groups are of equal size. If groups have size, 3 or 4 the algorithm returns a solution for any number of participants. Otherwise, the algorithm suggests a solution. We discuss how to construct solutions for unequal group sizes ( 4 and 5 , or 5 and 6 ) by adding participants to smaller solutions, or removing from them from larger solutions. Tables containing SGP and SGA solutions for up to 150 participants are provided in Appendix B . 2 Social Golfer problem and the Social Golfer problem with adjacent block sizes 2.1 The Social Golfer Problem The Social Golfer problem (which we refer to as SGP) [ 70 , 97 , 120 ] originated from the following question posed in 1998 to sci.op-research : 32 golfers play golf once a week, and always in groups of 4 . For how many weeks can they play such that no two players play together more than once in the same group? In fact the answer to this problem is ten weeks. We will show in Section 6.2 that the solution can be obtained using a combinatorial structure known as a Resolvable Group Divisible Design . The design for this case was originally constructed by Shen in [ 113 ] and independently solved by Colbourn in 1999 [ 41 ] . In 2004, Aguado recognised that the design would solve the problem and published a solution [ 22 ] . The problem can be generalised as follows (see [ 89 ] ): The SGP consists of scheduling n=g*s players into g groups of s players for w weeks so that any two players are assigned to the same group at most once in w weeks. Applications of the SGP include group teaching scenarios [ 95 , 38 , 87 ] , voting strategies [ 93 ] , and scheduling for sporting competitions [ 84 , 83 , 86 ] . Any instance of the SGP exhibits four types of symmetry arising from permuting the weeks, groups within weeks, players within groups and the players within the overall set of players. The SGP has been adopted by the Combinatorial Search community as a benchmark for testing advanced search and symmetry breaking techniques [ 55 , 61 , 62 , 26 , 51 ,