View Question
 ```Listed below is a eight(8) man golf schedule for seven (7)weeks in which no two (2) golfers play each other more than once. Using this criteria please expand the schedule to provide for twelve (12) golfers. Using Google I located "Symmetry Breaking and the Social Golfer" by Harvey Warwick but could not go further. Match # 1 1 2 VS 3 4 5 6 VS 7 8 9 10 VS 11 12 2 3 6 VS 4 5 1 7 VS 2 8 ?? 3 3 8 VS 1 5 4 7 VS 2 6 ?? 4 1 6 VS 2 5 4 8 vs 3 7 ?? 5 6 7 VS 1 3 2 4 VS 5 8 ?? 6 2 3 VS 1 8 4 6 VS 5 7 ?? 7 3 5 VS 6 8 1 4 VS 2 7 ? NOTE: I Have no idea how to price this: Is \$20.00 too much,little, just right?``` Request for Question Clarification by boquinha-ga on 16 Apr 2006 17:10 PDT ```Just to clarify--how many weeks long is your tournament with 12 players and how many times per week do you play? Thanks, Boquinha-ga``` Request for Question Clarification by boquinha-ga on 16 Apr 2006 18:13 PDT ```One more clarification--are you looking for unique pairings of golfers or unique opponents? For example, once golfers 1 and 2 have played together, could they then play against each other, say in a 1&3 vs. 2&4 match? Thanks, boquinha-ga```
 ```Hello ree1434-ga! I had no idea how many people have written about this exact problem until I did a simple search. There have been numerous papers written about the ?Social Golfer? problem, some with incredible mathematical detail. I did find a couple of sites that I believe answer this question very well. Looking over your initial example, I notice that each pairing is unique, but golfers may play *against* other golfers more than once during the sequence. This is also how the problem is addressed on the sites that I will reference. - - - - - - - - - - - - - - - - - - - - ?SYMMETRY BREAKING AND THE SOCIAL GOLFER? According to CiteSeer, Harvey Warwick?s article ?Symmetry Breaking and the Social Golfer? is a frequently referenced article relating to ?highly symmetric problems in a constraint programming context? (http://citeseer.ist.psu.edu/harvey01symmetry.html). Essentially, this ordering of golfing partners represents a very ordered and symmetrical problem. Developing an algorithm in order to determine the pairings would be a boon since it could be adapted to other problems. There is an article entitled ?Scheduling Golfers Locally? written by Ivan Dotu1 and Pascal Van Hentenryck of Brown University that deals with developing such an algorithm. You can read the entire PDF file at http://www.cs.brown.edu/~pvh/social.pdf. Honestly, I found the whole article very technical and confusing, but luckily elsewhere on their site there is a very nice summary with an interactive grid to help determine golf pairing, without all of the equations. The only equation that is discussed is a simple one that determines the maximum number of weeks that one could arrange pairs of golfers before there is a repeated pair. See http://www.cs.brown.edu/people/sello/golf.html for the full details. The basic equation is defined as follows: w = maximum number of weeks g = number of groups/pairings s = number of golfers W <= [(g*s)-1]/(s-1)] So in your example: g = 6 s = 2 w <= [(6*2)-1/(2-1) w <= [12-1]/(2-1) w <= 11 So the maximum number of weeks possible, maintaining unique weekly pairings, is 11. Of course, determining a shorter schedule would be simpler, but not all golfers would play together. Using the grid I mentioned above here is how an 11-week schedule would work out: Week 1 1 2 vs. 3 4 5 6 vs. 7 8 9 10 vs. 11 12 Week 2 1 3 vs. 2 4 5 7 vs. 6 8 9 11 vs. 10 12 Week 3 1 4 vs. 2 3 5 8 vs. 6 7 9 12 vs. 10 11 Week 4 1 5 vs. 2 6 3 9 vs. 4 10 7 11 vs. 8 12 Week 5 1 6 vs. 2 5 3 10 vs. 4 9 7 12 vs. 8 11 Week 6 1 11 vs. 2 12 3 5 vs. 4 6 7 9 vs. 8 10 Week 7 1 12 vs. 2 11 3 6 vs. 4 5 7 10 vs. 8 9 Week 8 1 7 vs. 2 8 3 11 vs. 4 12 5 9 vs. 6 10 Week 9 1 8 vs. 2 7 3 12 vs. 4 11 5 10 vs. 6 9 Week 10 1 9 vs. 2 10 3 7 vs. 4 8 5 11 vs. 6 12 Week 11 1 10 vs. 2 9 3 8 vs. 4 7 5 12 vs. 6 11 Whew! There they all are. Thank goodness there is a grid that helps work out such a complicated problem! I hope that this answers your question. If you have need of any further clarification please let me know how I can help. Thank you again! Oh, and welcome to Google Answers! Sincerely, Boquinha-ga Search strategy: symmetry breaking and the social golfer```