View Question
Q: Math Question for Golf Teaming ( Answered ,   1 Comment )
 Question
 Subject: Math Question for Golf Teaming Category: Computers > Algorithms Asked by: keithadler-ga List Price: \$25.00 Posted: 08 Apr 2004 10:59 PDT Expires: 08 May 2004 10:59 PDT Question ID: 327232
 ```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```
 keithadler-ga rated this answer: ```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```