Expert: Josh - 1/20/2009

Question
QUESTION: On our golf trip this spring, 12 of us will be playing for
6 days and we want to play with everyone at least once, or
twice, and hopefully not 3 times during the week.  I have used 12!/4!*8! which gives me 495 different combinations! I have 6 combinations in which we all play 1 to 3 times for the week. Could you assist me to come up with 6 combinations in which all 12 golfers would play only with each other a maximum of twice during the week?

ANSWER: Hi Ken,

I answered a very similar question for Aidan some time ago. You may wish to read the transcript below to see how it was done.

Basically, we have 66 possible pairings between 12 golfers. To get everybody to play each other once at least, we have to break each day into 2 or 3 sessions.

SCENARIO 1: 6 days, each with 2 (morning and afternoon) sessions.
===================================================================
Solution: Use the schedule prepared for Aidan, only replace the "Round-Session" labels with R1-S1, R1-S2, R2-S1, R2-S2, R3-S1, R3-S2, R4-S1, R4-S2, R5-S1, R5-S2, R6-S1, R6-S2. Refer to Appendix 2 below for instructions on how to import .csv file content into an Excel spreadsheet.
Drawback: You only get to play 10 players once and 1 player twice.

SCENARIO 2: 6 days, each with 3 (morning, noon and evening) sessions.
===================================================================
This schedule is better. You get to play 4 players once and 7 players twice. On the evening of day 4, the match-ups from earlier rounds will be repeated, but not in exactly the same order.

The content for this schedule is posted below in Appendix 1. Again, refer to comments given in Appendix 2 on how to import this into Excel. Hint: Remember to adjust the column width when you examine the table. Making each column narrower helps.

APPENDIX 1 - Copy content between the delimiters into a text editor. Rename the file as golf6x3.csv and open it using Microsoft Excel.
=====================================================================
(CSV CONTENT BEGINS AFTER THIS LINE)
Legend,,,,,,,,,Round-Session,,,,,,,,,,,,,,,Schedule,,,,,,,,,,,,
,,,,,Day 1,,,Day 2,,,Day 3,,,Day 4,,,Day 5,,,Day 6,,,,,,,,,,,,,,,,
,,,Match Ups,R1-S1,R1-S2,R1-S3,R2-S1,R2-S2,R2-S3,R3-S1,R3-S2,R3-S3,R4-S1,R4-S2,R4-S3,R5-S1,R5-S2,R5-S3,R6-S1,R6-S2,R6-S3,,,,A,B,C,D,E,F,G,H,I,J,K,L
A,Aidan,,AB,1,,,,,,,,,,,12,,,,,,,,,A,-,"1,12","2,18","3,13",4,"5,14",6,"7,15",8,"9,16",10,"11,17"
B,Bryan,,AC,,2,,,,,,,,,,,,,,,,18,,,B,"1,12",-,"3,13","2,18","5,14",4,"7,15",6,"9,16",8,"11,17",10
C,Chris,,AD,,,3,,,,,,,,,,13,,,,,,,,C,"2,18","3,13",-,"1,12",10,8,"9,16","11,17",4,"5,14",6,"7,15"
D,Dave,,AE,,,,4,,,,,,,,,,,,,,,,,D,"3,13","2,18","1,12",-,"11,17",10,8,"9,16","7,15",4,"5,14",6
E,Ernie,,AF,,,,,5,,,,,,,,,14,,,,,,,E,4,"5,14",10,"11,17",-,"1,12","2,18","3,13",6,"7,15","9,16",8
F,Frank,,AG,,,,,,6,,,,,,,,,,,,,,,F,"5,14",4,8,10,"1,12",-,"3,13","2,18","11,17",6,"7,15","9,16"
G,George,,AH,,,,,,,7,,,,,,,,15,,,,,,G,6,"7,15","9,16",8,"2,18","3,13",-,"1,12",10,"11,17",4,"5,14"
H,Harry,,AI,,,,,,,,8,,,,,,,,,,,,,H,"7,15",6,"11,17","9,16","3,13","2,18","1,12",-,"5,14",10,8,4
I,Issac,,AJ,,,,,,,,,9,,,,,,,16,,,,,I,8,"9,16",4,"7,15",6,"11,17",10,"5,14",-,"1,12","2,18","3,13"
J,John,,AK,,,,,,,,,,10,,,,,,,,,,,J,"9,16",8,"5,14",4,"7,15",6,"11,17",10,"1,12",-,"3,13","2,18"
K,Ken,,AL,,,,,,,,,,,11,,,,,,17,,,,K,10,"11,17",6,"5,14","9,16","7,15",4,8,"2,18","3,13",-,"1,12"
L,Larry,,BC,,,3,,,,,,,,,,13,,,,,,,,L,"11,17",10,"7,15",6,8,"9,16","5,14",4,"3,13","2,18","1,12",-
,,,BD,,2,,,,,,,,,,,,,,,,18,,,,,,,,,,,,,,,
,,,BE,,,,,5,,,,,,,,,14,,,
,,,BF,,,,4,,,,,,,,,,,,,
,,,BG,,,,,,,7,,,,,,,,15,,
,,,BH,,,,,,6,,,,,,,,,,,
,,,BI,,,,,,,,,9,,,,,,,16,
,,,BJ,,,,,,,,8,,,,,,,,,
,,,BK,,,,,,,,,,,11,,,,,,17
,,,BL,,,,,,,,,,10,,,,,,,
,,,CD,1,,,,,,,,,,,12,,,,,
,,,CE,,,,,,,,,,10,,,,,,,
,,,CF,,,,,,,,8,,,,,,,,,
,,,CG,,,,,,,,,9,,,,,,,16,
,,,CH,,,,,,,,,,,11,,,,,,17
,,,CI,,,,4,,,,,,,,,,,,,
,,,CJ,,,,,5,,,,,,,,,14,,,
,,,CK,,,,,,6,,,,,,,,,,,
,,,CL,,,,,,,7,,,,,,,,15,,,
,,,DE,,,,,,,,,,,11,,,,,,17,
,,,DF,,,,,,,,,,10,,,,,,,,
,,,DG,,,,,,,,8,,,,,,,,,,
,,,DH,,,,,,,,,9,,,,,,,16,,
,,,DI,,,,,,,7,,,,,,,,15,,,
,,,DJ,,,,4,,,,,,,,,,,,,,
,,,DK,,,,,5,,,,,,,,,14,,,,
,,,DL,,,,,,6,,,,,,,,,,,,
,,,EF,1,,,,,,,,,,,12,,,,,,
,,,EG,,2,,,,,,,,,,,,,,,,18
,,,EH,,,3,,,,,,,,,,13,,,,,
,,,EI,,,,,,6,,,,,,,,,,,,
,,,EJ,,,,,,,7,,,,,,,,15,,,
,,,EK,,,,,,,,,9,,,,,,,16,,
,,,EL,,,,,,,,8,,,,,,,,,,
,,,FG,,,3,,,,,,,,,,13,,,,,
,,,FH,,2,,,,,,,,,,,,,,,,18
,,,FI,,,,,,,,,,,11,,,,,,17,
,,,FJ,,,,,,6,,,,,,,,,,,,
,,,FK,,,,,,,7,,,,,,,,15,,,
,,,FL,,,,,,,,,9,,,,,,,16,,
,,,GH,1,,,,,,,,,,,12,,,,,,
,,,GI,,,,,,,,,,10,,,,,,,,
,,,GJ,,,,,,,,,,,11,,,,,,17,
,,,GK,,,,4,,,,,,,,,,,,,,
,,,GL,,,,,5,,,,,,,,,14,,,,
,,,HI,,,,,5,,,,,,,,,14,,,,
,,,HJ,,,,,,,,,,10,,,,,,,,
,,,HK,,,,,,,,8,,,,,,,,,,
,,,HL,,,,4,,,,,,,,,,,,,,
,,,IJ,1,,,,,,,,,,,12,,,,,,
,,,IK,,2,,,,,,,,,,,,,,,,18
,,,IL,,,3,,,,,,,,,,13,,,,,
,,,JK,,,3,,,,,,,,,,13,,,,,
,,,JL,,2,,,,,,,,,,,,,,,,18
,,,KL,1,,,,,,,,,,,12,,,,,,
(END CSV CONTENT)

Appendix 2 - Previous post
==========================
Subject:   permutations of 4 from 12
Question:  This is a practical question re golf four balls. I am going on a golfing holiday with 11 others and we will play 4 rounds . Is there a permutation were each player can play with each other player only playing with one player twice and with the other 10 once only. I have been struggling with this over the past few days with
no joy.

Answer:
Aidan,
There are 66 unique pairings according to my calculation (12!/(10!*2!)).

You need at least 11 rounds to get each player playing each other once. Assuming 18 holes per round, I guess you can divide each round into 3 sessions (morning, noon and evening) to get twelve pairing opportunities, say over four days.

It is possible for everyone to play one player one more time if you have 12 rounds (or sessions); provided the match-ups are selected from a hat in the final session without replacement. This simply means we cannot allow more than one person playing with Tiger at the same time even if he is everyone's favorite. Alternatively, you can repeat the match-up from one of the earlier rounds.

Below the dash line is a .csv file which contains a suggested schedule. You can copy the content into any text editor, save it as a "golfsche.csv" file, then open it as an Excel spreadsheet. Don't try to read this as is, everything has to line up for it to make sense.

Cheers,

--------------------------------------
Legend,,,,,,,,,Round-Session,,,,,,,,Schedule,,,,,,,,,,,,,,
,,,,,Day 1,,,Day 2,,,Day 3,,,Day 4,,,,,,,,,,,,,,,,,
,,,Match Ups,R1-S1,R1-S2,R1-S3,R2-S1,R2-S2,R2-S3,R3-S1,R3-S2,R3-S3,R4-S1,R4-S2,R4-S3,,,A,B,C,D,E,F,G,H,I,J,K,L,,
A,Aidan,,AB,1,,,,,,,,,,,,,A,-,1,2,3,4,5,6,7,8,9,10,11,,
B,Bryan,,AC,,2,,,,,,,,,,,,B,1,-,3,2,5,4,7,6,9,8,11,10,,
C,Chris,,AD,,,3,,,,,,,,,,,C,2,3,-,1,10,8,9,11,4,5,6,7,,
D,Dave,,AE,,,,4,,,,,,,,,,D,3,2,1,-,11,10,8,9,7,4,5,6,,
E,Ernie,,AF,,,,,5,,,,,,,,,E,4,5,10,11,-,1,2,3,6,7,9,8,,
F,Frank,,AG,,,,,,6,,,,,,,,F,5,4,8,10,1,-,3,2,11,6,7,9,,
G,George,,AH,,,,,,,7,,,,,,,G,6,7,9,8,2,3,-,1,10,11,4,5,,
H,Harry,,AI,,,,,,,,8,,,,,,H,7,6,11,9,3,2,1,-,5,10,8,4,,
I,Issac,,AJ,,,,,,,,,9,,,,,I,8,9,4,7,6,11,10,5,-,1,2,3,,
J,John,,AK,,,,,,,,,,10,,,,J,9,8,5,4,7,6,11,10,1,-,3,2,,
K,Kyle,,AL,,,,,,,,,,,11,,,K,10,11,6,5,9,7,4,8,2,3,-,1,,
L,Larry,,BC,,,3,,,,,,,,,,,L,11,10,7,6,8,9,5,4,3,2,1,-,,
,,,BD,,2,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,BE,,,,,5,,,,,,,
,,,BF,,,,4,,,,,,,,
,,,BG,,,,,,,7,,,,,
,,,BH,,,,,,6,,,,,,
,,,BI,,,,,,,,,9,,,
,,,BJ,,,,,,,,8,,,,
,,,BK,,,,,,,,,,,11,
,,,BL,,,,,,,,,,10,,
,,,CD,1,,,,,,,,,,,
,,,CE,,,,,,,,,,10,,
,,,CF,,,,,,,,8,,,,
,,,CG,,,,,,,,,9,,,
,,,CH,,,,,,,,,,,11,
,,,CI,,,,4,,,,,,,,
,,,CJ,,,,,5,,,,,,,
,,,CK,,,,,,6,,,,,,
,,,CL,,,,,,,7,,,,,
,,,DE,,,,,,,,,,,11,
,,,DF,,,,,,,,,,10,,
,,,DG,,,,,,,,8,,,,
,,,DH,,,,,,,,,9,,,
,,,DI,,,,,,,7,,,,,
,,,DJ,,,,4,,,,,,,,
,,,DK,,,,,5,,,,,,,
,,,DL,,,,,,6,,,,,,
,,,EF,1,,,,,,,,,,,
,,,EG,,2,,,,,,,,,,
,,,EH,,,3,,,,,,,,,
,,,EI,,,,,,6,,,,,,
,,,EJ,,,,,,,7,,,,,
,,,EK,,,,,,,,,9,,,
,,,EL,,,,,,,,8,,,,
,,,FG,,,3,,,,,,,,,
,,,FH,,2,,,,,,,,,,
,,,FI,,,,,,,,,,,11,
,,,FJ,,,,,,6,,,,,,
,,,FK,,,,,,,7,,,,,
,,,FL,,,,,,,,,9,,,
,,,GH,1,,,,,,,,,,,
,,,GI,,,,,,,,,,10,,
,,,GJ,,,,,,,,,,,11,
,,,GK,,,,4,,,,,,,,
,,,GL,,,,,5,,,,,,,
,,,HI,,,,,5,,,,,,,
,,,HJ,,,,,,,,,,10,,
,,,HK,,,,,,,,8,,,,
,,,HL,,,,4,,,,,,,,
,,,IJ,1,,,,,,,,,,,
,,,IK,,2,,,,,,,,,,
,,,IL,,,3,,,,,,,,,
,,,JK,,,3,,,,,,,,,
,,,JL,,2,,,,,,,,,,
,,,KL,1,,,,,,,,,,,

---------- FOLLOW-UP ----------

QUESTION: Josh,

If you could, please assist me with pairings for 6 days of golf, one session each day? We will have 12 golfers and play in foursomes.  I already have tentative pairings with 3 golfers playing once or twice with the other golfers; 4 golfers playing three times with one other golfer, then once or twice with the others; and 5 golfers playing three times with two golfers, then once or twice with the other.
Can you show me the pairings which will have each of the 12 golfers play one session each day, in a foursome, and not have to play any of the other 11 golfers three times that week?  One pairing example would be as follows:
        Team #1:    1   2   3   4
Day #1   Team #2:    5   6   7   8
        Team #3:    9   10  11  12

In this example, golfer #1 will play with golfers #2,#3 and #4 the first day, and could only play with them once more over the next 5 days. (one session per day)

Thanks for your help........  

Answer
Hi Ken,

This is a difficult question which I do not have the answer to. The number of ways in which three playing groups of 4 can be formed is 12!/(4!8!) x 8!/(4!4!) which amounts to 34650 combination. There are 34650!/(6!(34650-6)!) ways of making a random 6 day schedule. Of course, very few (if any) will actually meet your criteria.

The best that I can come up with is a four day schedule in a "three playing group of four" format without two players belonging to the same playing group on more than two occasions (see table in the attached image).

My approach is based on constructing an occupancy matrix, where a "1" is added to the intersection of row i, column j, each time player i and j are placed in the same group. The typical contribution of a playing group to this matrix is illustrated in blue dotted line.

You can see that it gets pretty crowded by day 4 (see middle matrix), given the complex dependencies, it is difficult to see how further contributions can be added without exceeding the threshold (of 3 encounters between two given players).

The problem may have a solution if we can find a matrix M (see bottom matrix in the attached image) satisfying the following constraints:
- M is a symmetric matrix, i.e., M(i,j)=M(j,i);
- Elements on the main diagonal are zero, i.e., M(i,i)=0 for i=1 to 12
- All rows and columns must add to 18, with elements chosen from the set {0,1,2}; no other values are permitted.
- Each row contains seven "2"s and four "1"s. [since each person must face 4 players once and 7 other players twice]

I am sure there are better ways of going about this -- to show whether a solution exists or not -- that I am not aware of. Finding a solution by inspection is no easy feat for an average person like me.

Enjoy your game!