I cannot figure out the math for this one!  I have 32 golfers I play
with and we are broken into teams of 4 players (for 8 total teams).  I
can determine easily using google that '32 choose 4' results in 35,960
different team combinations.  What I'd like to do, is come up with a
unique list of games that can be played where no two people are ever
on the same team.  I cannot figure out the math for this.  I assume
that the answer is 10, since 32/(4-1) =
10.666 but I cannot figure out the 10 different team configurations. 
Please provide me with an algorithm or code in Java, VB, VBA that can
generate the teams for these unique games.

---

Request for Question Clarification by mathtalk-ga on 08 Apr 2004 13:28 PDT

Hi, keithadler-ga:

You have posed a difficult, and as far as I know, unsolved problem in
combinatorics.

This is the Social Golfer Problem, to find the maximum number of
occasions on which foursomes (or some other size grouping) can be
scheduled so that everyone plays on every occasion, but no pair of
golfers are teamed together more than once.

In the case of 8 foursomes (32 golfers in all), you have already
figured out that 10 "games" is the most that can be scheduled for any
one golfer, and hence for the party as a whole, if games are played
once a day, for 10 days.

A Web site devoted to this problem has been created by Warwick Harvey:

[Social Golfer Problem]
http://4c.ucc.ie/~tw/csplib//prob/prob010/index.html

and a summary of the best results known to him are tabulated here:

[Warwick's Results Page for the Social Golfer Problem]
http://www.icparc.ic.ac.uk/~wh/golf/

Note that the entries for 8 groups of 4 golfers gives a lower bound of
9 "games" (actually parallel classes of foursomes which cover the 32
golfers) and an upper bound of 10 (just as you've already reasoned for
yourself).

These problems tend to be computationally difficult because of a high
degree of symmetry in the potential range of "solutions".  For this
reason no one has yet been able to pin down, as far as I know, whether
9 or 10 "games" are the maximum feasible schedule.

I could provide you with a solution for 9 "games" (assigning nine sets
of 8 foursomes, each of which exhausts the 32 golfers, with no two
golfers playing together more than once throughout the nine sets).

For a similar sort of problem, in the context of a dinner club
scheduling four couples per table, see here:

[Q: Unique combinations of 4 numbers between 1 to "N"]
http://answers.google.com/answers/threadview?id=274891

regards, mathtalk-ga

---

Clarification of Question by keithadler-ga on 08 Apr 2004 17:53 PDT

How do I pay you?  This is my answer and it's perfect.

Thanks,

Keith

---

Request for Question Clarification by mathtalk-ga on 09 Apr 2004 03:38 PDT

Hi, Keith:

Thanks, I'll dress it up a bit with a construction of a 9 games
schedule and post as an Answer.

regards, mathtalk-ga

---

Clarification of Question by keithadler-ga on 09 Apr 2004 06:40 PDT

Great, you can just post the text "see links".  Quite honestly, this
is more than I had hoped for.

Hi, keithadler-ga:

In addition to the links already provided above, I wanted to give an example.

9 rounds of golf foursomes among 32 golfers, such that no two golfers
play together in the same foursome more than once, can be arranged as
follows.

First divide the 32 golfers into four groups of 8 golfers.  Then 8
rounds can be scheduled by taking combinations which draw one golfer
from each of the four groups.  [The existence of such an 8 round
schedule is equivalent to the existence of three mutually orthogonal
Latin squares of order 8. There are formulas behind such a
construction which involve a fancy kind of arithmetic (finite field of
order 8).  Details available on request.]

A final 9th round can then be added by dividing each group of 8 into
two foursomes.  This round is the only one that puts players of the
same group of 8 together in a foursome.

Details of a 9 round schedule for 32 golfers in foursomes
=========================================================

Let the four groups of 8 golfers be labelled like this:

{A1,A2,A3,A4,A5,A6,A7,A8}

{B1,B2,B3,B4,B5,B6,B7,B8}

{C1,C2,C3,C4,C5,C6,C7,C8}

{D1,D2,D3,D4,D5,D6,D7,D8}

All rounds will then consist of 8 foursomes.

Round 1:
========

{ {A1,B1,C1,D1}, {A2,B2,C2,D2}, {A3,B3,C3,D3}, {A4,B4,C4,D4},

  {A5,B5,C5,D5}, {A6,B6,C6,D6}, {A7,B7,C7,D7}, {A8,B8,C8,D8} }


Round 2:
========

{ {A1,B2,C3,D5}, {A2,B1,C4,D6}, {A3,B4,C1,D7}, {A4,B3,C2,D8},

  {A5,B6,C7,D1}, {A6,B5,C8,D2}, {A7,B8,C5,D3}, {A8,B7,C6,D4} }


Round 3:
========

{ {A1,B3,C5,D4}, {A2,B4,C6,D3}, {A3,B1,C7,D2}, {A4,B2,C8,D1},

  {A5,B7,C1,D8}, {A6,B8,C2,D7}, {A7,B5,C3,D6}, {A8,B6,C4,D5} }


Round 4:
========

{ {A1,B4,C7,D8}, {A2,B3,C8,D7}, {A3,B2,C5,D6}, {A4,B1,C6,D5},

  {A5,B8,C3,D4}, {A6,B7,C4,D3}, {A7,B6,C1,D2}, {A8,B5,C2,D1} }


Round 5:
========

{ {A1,B5,C4,D7}, {A2,B6,C3,D8}, {A3,B7,C2,D5}, {A4,B8,C1,D6},

  {A5,B1,C8,D3}, {A6,B2,C7,D4}, {A7,B3,C6,D4}, {A8,B4,C5,D2} }


Round 6:
========

{ {A1,B6,C2,D3}, {A2,B5,C1,D4}, {A3,B8,C4,D1}, {A4,B7,C3,D2},

  {A5,B2,C6,D7}, {A6,B1,C5,D8}, {A7,B4,C8,D5}, {A8,B3,C7,D6} }

  
Round 7:
========

{ {A1,B7,C8,D6}, {A2,B8,C7,D5}, {A3,B5,C6,D8}, {A4,B6,C5,D7},

  {A5,B3,C4,D2}, {A6,B4,C3,D1}, {A7,B1,C2,D4}, {A8,B2,C1,D3} }


Round 8:
========

{ {A1,B8,C6,D2}, {A2,B7,C5,D1}, {A3,B6,C8,D4}, {A4,B5,C7,D3},

  {A5,B4,C2,D6}, {A6,B3,C1,D5}, {A7,B2,C4,D8}, {A8,B1,C3,D7} }


Round 9:
========

{ {A1,A2,A3,A4}, {B1,B2,B3,B4}, {C1,C2,C3,C4}, {D1,D2,D3,D4},

  {A5,A6,A7,A8}, {B5,B6,B7,B8}, {C5,C6,C7,C8}, {D5,D6,D7,D8} }


More generally...
=================

If there are some other number N of golfers, then the "test" that you thought up:

N is divisible by 4  and   N-1 is divisible by 3

is both necessary and sufficient for a "nice" solution to exist, i.e.
a schedule in which the N golfers can be "partitioned" into foursomes
on (N-1)/3 occasions in such a way that every pair of golfers plays a
round together exactly once.

This is not the hardest or messiest thing to prove I've ever come
across, but it doesn't lend itself to a quick elegant proof either. 
Suffice it to say that a mathematician name Richard M. Wilson
pioneered the techniques for proving such things exist for all
sufficiently large N (they go by the name of "resolvable 2-designs of
block size 4") back in the mid 1970's, and from there it was just a
matter of supplying enough "small" examples to make sure there are no
exceptions.

Here's a reference for those "nice" cases, like when N = 28 or 40.

The trouble is that you asked about N = 32, and unfortunately 3 does
not go into 31 a whole number of times.  So N = 32 is one of the "not
nice" cases.  The schedule presented above seems rather tight; at the
end each player has exactly for others that they've been teamed with,
but all for of those have teamed with one another, so not only can
another round not be scheduled, it is not even possible to put
together one more foursome (without repeating some pairings).  My
instinct is that 10 rounds are not possible, though it is no proof of
this merely to give the example of 9 rounds shown above.

Thanks for posting the interesting Question. Any Clarifications
needed, I'll be glad to help.

regards, mathtalk-ga

The answer was more than I could have hoped for.  Not only did it give
me what I wanted, but the researcher obviously cared more about
prividing the answer than the nominal fee assosiated with it.  I will
certainly use this service again.

Thanks, Keith.  Here's the reference I meant to add to the discussion above:

A. E. Brouwer, Block Designs, in: "Handbook of Combinatorics",
R.L. Graham, M. Grötschel and L. Lovász, eds,
North Holland (1995), Chapter 14, pp. 693-745.

-- mathtalk-ga