The Social Golfer Problem (SGP) is a combinatorial optimisation
problem. The task is to schedule g × p golfers
in g groups of p players
for w weeks such that no two golfers play in the same
group more than once. An instance of the SGP is denoted
by the triple g-p-w. The original problem asks for the
maximal w such that the instance 8-4-w can
After the original SGP instance was first posted to the discussion
group sci.op-research in 1998, a solution for
9 weeks was soon found. It was also clear that no solution for
11 weeks could exist.
Proof: Suppose w>=11, and observe the
schedule of an arbitrary but fixed player α. Each week,
α plays in a group with 3 distinct other players.
To play for 11 weeks, α would have to partner 3 × 11
> 31 other players.
Whether there exists a solution for 10 weeks was an open question
for several years,
Aguado constructed an explicit solution for the 8-4-10
instance in 2004 (txt):