Figure 1: KTS(9). Nine golfers (points) play for four days (colors) in groups of 3 (triangles).
Ed Pegg Jr., August 14, 2007
In 1850, Reverend Thomas Kirkman sent a query to the readers of a popular math magazine, Lady's and Gentleman's Diary.
Fifteen young ladies in a school walk out 3 abreast for seven days in succession: it is required to arrange them daily, so that no two will walk twice abreast.
Arthur Cayley and Kirkman both published solutions. Problems of this type were called Kirkman Triple Systems in his honor. In a related problem, Jakob Steiner asked for 35 blocks of triples from A-O with every pair occuring in exactly one block. These solutions are called a Steiner Triple System, or STS(15) for this case. When the triples can be arranged in parallel groups, so that all 15 students occur in each class, it is called either a Resolvable Steiner Triple System (RSTS) or a Kirkman Triple System (KTS). Steiner systems are not always resolvable! There are 80 unequivalent (nonisomorphic) solutions to STS(15), but only 7 solutions to KTS(15). It's also called a Resolvable Balanced Incomplete Block Design, or RBIBD(15,3,1) -- 15 students, sets of 3, any pair occurs 1 time.
It's also called the Social Golfer problem. Fifteen golfers A-O each play every day in groups of three, so that no two golfers plays more than once with each other. Can they play for 7 days? One of the 7 solutions to that, as well as the solution to KTS(15) and RBIBD(15,3,1), is below.
James Sylvester noted that there were 455 possible triples, and wondered is the 15 schoolgirls could repeat their task for 13 weeks, without ever repeating a triple. In 1974, R. H. F. Denniston solved the problem. In 2005, Tom Johnson used Denniston's solution for the musical composition Kirkman's Ladies.1pm 2pm 3pm 4pm 5pm
Day1 ABC DEF GHI JKL MNO
Day2 ADG BEJ CFM HKN ILO
Day3 AEN BDO CHL FIK GJM
Day4 AIM BGL CDK EHO FJN
Day5 AHJ BKM CEI DLN FGO
Day6 AFL BIN CJO DHM EGK
Day7 AKO BFH CGN DIJ ELM
How about 18 golfers (A-I & a-i), playing in triples? Can they play for 8 days? They can't play for 9 days, since each golfer can only meet 17 other golfers. In eight days, each golfer misses playing with one of the other golfers, so I use 9 couples, Aa-Ii, with each golfer playing with everyone but their spouse. When it's not possible for all golfers to play with each other, and there are no repetitions, it's called a Kirkman packing design. Other names: 3-Resolvable Group Divisible Design (3-RGDD) of type 29, Oberwolfach problem OP(36), and Nearly Kirkman Triple System NKTS(18).
6am 7am 8am 9am 1pm 2pm
Day1 ABC DEF GHI ahf dbi gec
Day2 Abc Def Ghi aHF dBI gEC
Day3 abC deF ghI AHf DBi GEc
Day4 aBc dEf gHi AhF DbI GeC
Day5 ADG BEH CFI aei bfg cdh
Day6 Adg Beh Cfi aEI bFG cDH
Day7 adG beH cfI AEi BFg CDh
Day8 aDg bEh cFi AeI BfG CdH
Can 9 golfers (A-I) play in threesomes for 4 days? That's KTS(9), with solution ABC DEF GHI, AHF DBI GEC, ADG BEH CFI, AEI BFG CDG. You might notice a lot of similarity between KTS(9) and NKTS(18). This is deliberate. NKTS(18) uses what is called a doubling construction on KTS(9) (Rees and Wallis, 2002). A pictorial version of KTS(9) is below.
Figure 1: KTS(9). Nine golfers (points) play for four days (colors) in groups of
3 (triangles).
Can 12 golfers play in triples for 5 days? No, it's impossible -- can anyone find an elegant non-existance proof? 4 days is possible, as shown below.
Figure 2: Twelve golfers (points) play for 4 days (colors) in groups of 3 (lines)
Can 21 golfers play in threesomes for 10 days? Yes, as KTS(21). Perfect solutions exist for KTS(6v+3), when v>0. There are 63,745 nonisomorphic Kirkman triple systems of order 21.
Day0 ABF EGM DKR INP CJT HOU LQS
Day1 DEJ HIK BNO AQR CLU FMS GPT
Day2 AHL JKO EIQ CNR BGS DMT FPU
Day3 BCD FHN ELP GOQ AKT IMU JRS
Day4 EFK IGL COM BRP AJU DNS HQT
Day5 BIJ KLM FGR AOP CHS ENT DQU
Day6 CAE DIO FJQ HMR BLT GNU KPS
Day7 FDL GHJ AMN CPQ BKU EOS IRT
Day8 CGK LJN DHP BMQ AIS FOT ERU
Day9 STU ADG BEH CFI JMP KNQ LOR
Can 24 golfers play in threesomes for 11 days? Yes, by deleting a point from KTS(9), a method by Kotzig and Rosa can be used to construct NKTS(24). Rees and Wallis describe the construction as "self-explanatory," but I haven't figured it out. The following solution only works for 10 days, but they can finish up with foursomes on the last day.
Day0 ABC DEF GHI JKL MNO PQR STU VWX
Day1 JOT ESB API DML HCV QWN FKU GRX
Day2 DVK SFO JQI EHL PTG WRC BMU ANX
Day3 EGM FBV DWI SPL QKA RNT OHU JCX
Day4 SAH BOG ERI FQL WMJ NCK VPU DTX
Day5 FJP OVA SNI BWL RHD CTM GQU EKX
Day6 BDQ VGJ FCI ORL NPE TKH AWU SMX
Day7 OEW GAD BTI VNL CQS KMP JRU FHX
Day8 VSR AJE OKI GCL TWF MHQ DNU BPX
Day9 GFN JDS VMI ATL KRB HPW ECU OQX
Day10 AFMR BNHJ CPOD EQVT GKSW IXUL
For 27 golfers playing in threesomes for 13 days, here is a doubly resolvable design. Taking all the rows gives a solution. Alternately, taking all the columns gives a solution. This sort of system is known as a Kirkman square.
There are many ways for social golfers to play in threesomes. How about foursomes?YZ+ ABC DEF GHI JKL MNO PQR STU VWX
MTR DW+ SLZ ANU VBF EOY GJP IXC HKQ
JQO PIZ VKR SWC BLY AT+ DGM FUX EHN
SBX KUY JE+ ARZ GTC DHL OFI NQW MPV
AHF JNR QCY PK+ GXZ MBI SVD ULO TWE
GNL SHO PTX WIY VQ+ MFZ CRU BEK ADJ
PWU GB+ VOZ DQX AEI HRY KNT JMS LCF
VEC NXY MH+ DUZ JWF GKO PSA RIL QTB
DKI MQU TFY SN+ JCZ PEL WBH VAG XOR
MEX JTI DBR AQL VHU PNF OC+ KWZ SGY
GQF AWO VNI SER MKC JBU LX+ HTZ PDY
VTL SKF PBO JHX GWR DNC EQZ MAY IU+
PHC MWL GEU DTO AKX SQI JVY FR+ BNZ
Can 16 golfers each play in foursomes for 5 days? This is sometimes called a resolvable Steiner quadruple system (RSQS). ABCD EFGH IJKL MNOP, AEIM BFJN CGKO DHLP, AFKP BELO CHIN DGJM, AGLN BHKM CEJP DFIO, AHJO BGIP CFLM DEKN is a solution. Below is a visual version of this solution.
Figure 3: Sixteen golfers (points) play for 5 days (colors) in groups of 4 (lines).
How long can 20 golfers play in foursomes? It turns out that 6 days isn't possible, it would be a 4-RGDD of type 210, which doesn't exist. I don't know of a clever proof of this. Five days is possible, as shown below.
24 golfers can play in foursomes for 7 days.Day1 ABCD EFGH IJKL MNOP QRST
Day2 AEIM BFJQ CGNR DKOS HLPT
Day3 AFOT BELR CIPS DGJM HKNQ
Day4 AJPR BHMS CEKT DFIN GLOQ
Day5 ALNS BGIT CHJO DEPQ FKMR
Day1 ABKU IJSE QRCM DGFX HLNO PTVW
Day2 ACLV IKTF QSDN EHGR BMOP JUWX
Day3 ADMW ILUG QTEO FBHS CJNP KRVX
Day4 AENX IMVH QUFP GCBT DJKO LRSW
Day5 AFOR INWB QVGJ HDCU EKLP MSTX
Day6 AEPS IOXC QWHK BEDV FJLM NRTU
Day7 AHJT IPRD QXBL CFEW GKMN OSUV
28 golfers can play in foursomes for 9 days. If quadruples are picked so that every pair occurs once, S(2, 4, 28), a Steiner 2-design is the solution, and there are 4466 such solutions. From these, there are 7 different resolvable designs, two of them coming from the Ree unital. Once of these solutions gives a schedule for our golfers.
Day1 ABCD EFGH IJKL MNab cdef ghij klmn
Day2 AEgk BFMc Ndhl GIem HJai CKbn DLfj
Day3 AFjn BEae bfim HKcl GLMh CINk DJdg
Day4 AIci BJNn EKMj FLdm begl CGaf DHhk
Day5 AGbd BHgm ELNi achn FKfk CJej DIMl
Day6 AKeh BLbk FIag EJfl Ncjm CHMd DGin
Day7 AHNf BGjl FJbh Meik EIdn CLcg DKam
Day8 ALal BKdi GJck Mfgn HIbj CEhm DFNe
Day9 AJMm BIfh CFil DEbc GKNg HLen adjk
32 golfers playing in foursomes for 10 days. This problem has been on the Social Golfer Problem page, in a 1998 sci.ops-research usenet posting, in mathpages.com, and in Google answers. Lots of wrong answers, unfortunately. The problem was first solved by Hao Shen in 1996, and independently solved by Charles Colbourn in 1999. In 2004, Alejandro Aguado came across the problem, and realized 4-RGDD (Resolvable Group Divisible Design) of type 216 would solve the problem, and used Coulbourn's paper to produce "A 10 Days Solution to the Social Golfer Problem." In this solution, couples Aa-Oo all play once with everyone but their spouse.
Day0 ABCD EFGH IJKL MNPO abcd efgh ijkl mnop
Day1 AEIm BgcH DFKp kPdf Maei ChbG jNoL lJnO
Day2 Alof Bhkm DNGi FaLO MbHK CPeJ Ejcp gIdn
Day3 AciL BjdK DkbJ FgoP fGOp CIla EhMn NeHm
Day4 AgNK BElP DIoH hdiO beLp Cjfm FMcJ kaGn
Day5 AhJp BFin DcmO INbf leGK CMod EgkL jPaH
Day6 AFde BoGJ DEaf hlNc PiKm CHLn gjbO IkMp
Day7 APbn BNap DglM koce fHiJ CEKO FhIj dGLm
Day8 AjMG BIeO DhPL gaJm cfKn CFkN Eobi ldHp
Day9 AkHO BMfL Djen Flbm IPcG Cgip ENdJ hoaK
36 golfers in foursomes can play for 11 days. This is a 4-RGDD of type 218, but I don't yet have that solution.
Here is a table best possible solutions, along with links.
| 2 golfers per group | 3 golfers per group | 4 golfers per group | |
|---|---|---|---|
| 4 groups | |||
| 5 groups | |||
| 6 groups | |||
| 7 groups | |||
| 8 groups | |||
| 9 groups |
An excellent site with complete solutions for round robin games, tennis doubles tournaments, and whist/bridge tournaments is at Round Robin Tournament Scheduling. These tournaments make a good basis for logic puzzles. Below is a sample.
Sixteen social golfers (A to P) play in foursomes over five days. After the first day, they pick out the tee-times on days where their schedules are tight. Fill out the rest so the each golfer plays once each day, and plays exactly once with every other golfer. Starting hint: on day 5, golfer D cannot play with A, B, or C.
day1 day2 day3 day4 day5
9am ABCD GIP M IH G
1pm EFGH N FOD EJ JOB
3pm IJKL CEL PLH AK AM
5pm MNOP DK NK B CF
I mentioned in my column about Golomb Rulers that OGR-24 used a distributed system involving 41,805 people and 4 years to verify a 1967 result by John P. Robinson and Arthur J. Bernstein. For the 32 golfer problem, lots of computer time has been used over the past 9 years to find non-optimal answers for an already-solved question.
Never trust the brute-force power of a computer network to do the job of a combinatorialist.
Myra Cohen, Charles Colbourn, Lee Ives, and Alan Ling. "Kirkman Triple Systems of Orders 21 and 27," http://citeseer.ist.psu.edu/301876.html.
Charles Colbourn and Jeffrey Dinitz, Handbook of Combinatorial Designs, 2nd Ed. CRC Press, 2007.
Marialuisa de Resmini, "There Exist at least Three Non-Isomorphic S(2,4,28)'s." J. of Geom 16, 1981, p 148-151.
Richard DeVenezia, "Round Robin Tournament Scheduling", http://www.devenezia.com/downloads/round-robin/index.html.
Steven Furino, Ying Miao, and Jianxing Yin. Frames and Resolvable Designs. CRC Press, 1996.
Warwick Harvey. "The Social Golfer Problem." http://www.cs.brown.edu/~sello/golf.html.
Anton Kotzig and Alexander Rosa. "Nearly Kirkman Systems." Cong Num 10, p. 607-614, 1974.
V.Krcadinac. "Steiner 2-designs S(2,4,28) with nontrivial automorphisms." Glasnik Matematicki 37, p. 259-268, 2002. [dvi, ps, pdf]
Rolf Rees and W. D. Wallis. "Kirkman Triple Systems and their Generalization: A Survey." Designs 2002, p. 317-368.
Hao Shen and Jiaying Shen. "Existence of Resolvable Group Divisible Designs with Block Size 4." Disc Math 254, p. 513-525, 2002.
Comments are welcome. Please send comments to Ed Pegg Jr. at ed@mathpuzzle.com.
Ed Pegg Jr. is the webmaster of mathpuzzle.com. He works at Wolfram Research, Inc. as an associate editor of MathWorld. He is also a math consultant for the TV show Numb3rs.