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 composition1pm 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 2^{9}, Oberwolfach problem OP(3^{6}), 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(6*v*+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 2^{10}, 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 2^{16} 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 2^{18}, 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*.