Round Robin Tournament Scheduling

9 golfers - 4 games

Lee Perriam · 18 · 19512

Lee Perriam

  • Newbie
  • *
    • Posts: 3
on: October 05, 2006, 05:48:51 PM
We have a group of nine golfers playing four rounds of golf in 3 x 3 balls.

Is it possible to arrange the groups of three so that everyone plays with everyone else at least once and no one has to play with the same person more than twice?


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1140
Reply #1 on: October 06, 2006, 03:33:58 AM
Lee,

I am surprised that scheduling golf threesomes has not been raised here before. Anyway, the answer to your question is yes. With four rounds of threesomes it's possible to arrange that everyone plays everyone else exactly once.

(G F A)  (B D C)  (E H I)
(F C H)  (I G D)  (A E B)
(B I F)  (D A H)  (E C G)
(F D E)  (H B G)  (C I A)


The example above is the first in a whole series of threesome schedules.  If the number of players is three more than an a multiple of 6 then the all-plays-all-exactly-once property is always possible.  The next example is 15 players, which is famously known in mathematics as Kirkman's Schoolgirl problem (search the internet for more info on this, and you will find out how the schedule below can be constructed).

(K O H)  (L N J)  (E A G)  (F I C)  (D M B)
(B H N)  (A K I)  (F L D)  (O G C)  (M J E)
(M K L)  (O D J)  (G N I)  (E F H)  (B C A)
(C M N)  (H J G)  (L O A)  (I D E)  (K B F)
(L B G)  (N E K)  (O I M)  (H C D)  (J A F)
(I L H)  (A D N)  (C J K)  (G F M)  (B E O)
(M H A)  (E C L)  (J I B)  (D G K)  (N F O)



Below is the third in the series for 21 players.

(G F T)  (B I J)  (A U D)  (O S L)  (Q H K)  (P R M)  (N E C)
(K I U)  (T M H)  (S C B)  (J R L)  (A Q E)  (F P N)  (D O G)
(H I R)  (L B D)  (T O P)  (U G Q)  (K A C)  (S J N)  (E F M)
(A N M)  (E L P)  (S T D)  (G C R)  (U J H)  (I F Q)  (B K O)
(I P A)  (L U T)  (C O M)  (H B F)  (Q R S)  (J D E)  (N K G)
(E H G)  (I D C)  (O N R)  (M S U)  (T A J)  (K F L)  (Q B P)
(M L I)  (Q C T)  (F U O)  (D N H)  (R A B)  (P J G)  (K E S)
(C L H)  (E U R)  (N T I)  (D P K)  (F A S)  (O Q J)  (M G B)
(C P U)  (B T E)  (H O A)  (G S I)  (J M K)  (R D F)  (L Q N)
(R K T)  (D M Q)  (C J F)  (L G A)  (P H S)  (I E O)  (U N B)



Hope that helps,

Ian.


Lee Perriam

  • Newbie
  • *
    • Posts: 3
Reply #2 on: October 06, 2006, 09:32:05 AM
That's very useful. Thank you very much


mike G

  • Newbie
  • *
    • Posts: 2
Reply #3 on: October 24, 2006, 11:38:48 PM
now lets say that there are 10 players (2 groups of 5).  What are the pairings for 5 and that all players play with the same number of rounds with each person.  How many rounds would we need to play if we were to play each person 4 times each and how many for 5 times each?

Let me know.  Thanks

Mike G


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1140
Reply #4 on: October 25, 2006, 05:22:44 AM
If there are m groups of k players and you want them all to play each other at least t times each then you need at least

r = t*(mk-1) / (k-1)

rounds.  Note that I say at least.  Clearly if r is not a whole number then you will need to increase it to the next highest whole number or may be more.  Even if you find whole number solutions for all the unknowns in the equation above, then there is no guarantee that you will be able to construct a schedule, for some combinations it's just not possible to make things work.  Your values of m=2 and k=5 are a good example of this, while t=4 and r=9 fit the equation perfectly the 9 round schedule is actually impossible.   You would need double up to 18 rounds when you could get everyone playing each other 8 times.

Ian.


mike G

  • Newbie
  • *
    • Posts: 2
Reply #5 on: October 25, 2006, 09:52:34 AM
I appreciate it.  The only way to make that happen would to spend an extra week together and I don't think that the wife would like that very much.

Mike G


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1140
Reply #6 on: October 26, 2006, 04:34:05 AM
Mike,

My comments above relate to the situation where everyone plays everyone else the same number of times.  However there are other things you could do.  How about dividing your 10 players into 5 teams of 2 players each.  If the players are A to J, then make the teams up like this

(A B) (C D) (E F) (G H) (I J)


and then play the schedule below.

(B D F H I)   (A C E G J)
(B C E G I)   (A D F H J)
(A D E G I)   (B C F H J)
(A D E H J)   (B C F G I)
(B D E H I)   (A C F G J)
(B D F G J)   (A C E H I)
(A C F H I)   (B D E G J)
(A D F G I)   (B C E H J)


In the 8 rounds each player will play with all players from opposing teams exactly 4 times, and never play with their own team mate.

Ian.


BG

  • Newbie
  • *
    • Posts: 5
Reply #7 on: April 14, 2011, 05:24:18 PM
I am looking for the table that shows the threesome pairings for a total of 33 players.  Does anyone have that table?


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1140
Reply #8 on: April 15, 2011, 03:18:52 AM
Table is below, each of the 16 rows is a round, 11 threesomes per round.  Each player plays with all 32 possible partners exactly once.  It would be a good idea to randomize the tee-off order of the threesomes in each round to prevent player 1 always being the first on the course.

Hope that helps.

(1 2 18) (3 4 5)  (19 21 20) (6 10 14) (22 30 26) (7 12 17) (23 33 28) (15 8 13) (31 29 24) (11 16 9) (27 25 32)
(1 3 19) (2 4 21)  (18 5 20) (7 11 15) (23 31 27) (6 16 29) (22 13 32) (14 12 25) (30 9 28) (10 8 33) (26 17 24)
(1 4 20) (2 5 19)  (18 3 21) (8 12 16) (24 32 28) (10 9 31) (26 15 25) (6 17 27) (22 11 33) (14 13 23) (30 7 29)
(1 5 21) (2 3 20)  (18 4 19) (9 13 17) (25 33 29) (14 11 24) (30 8 27) (10 7 32) (26 16 23) (6 15 28) (22 12 31)
(1 6 22) (7 8 9)  (23 25 24) (2 10 30) (18 14 26) (3 16 13) (19 29 32) (11 4 17) (27 33 20) (15 12 5) (31 21 28)
(1 7 23) (6 8 25)  (22 9 24) (3 11 31) (19 15 27) (2 12 33) (18 17 28) (10 16 21) (26 5 32) (14 4 29) (30 13 20)
(1 8 24) (6 9 23)  (22 7 25) (4 12 32) (20 16 28) (14 5 27) (30 11 21) (2 13 31) (18 15 29) (10 17 19) (26 3 33)
(1 9 25) (6 7 24)  (22 8 23) (5 13 33) (21 17 29) (10 15 20) (26 4 31) (14 3 28) (30 12 19) (2 11 32) (18 16 27)
(1 10 26) (11 12 13)  (27 29 28) (2 14 22) (18 6 30) (15 4 9) (31 25 20) (7 16 5) (23 21 32) (3 8 17) (19 33 24)
(1 11 27) (10 12 29)  (26 13 28) (3 15 23) (19 7 31) (14 8 21) (30 5 24) (6 4 33) (22 17 20) (2 16 25) (18 9 32)
(1 12 28) (10 13 27)  (26 11 29) (4 16 24) (20 8 32) (2 17 23) (18 7 33) (14 9 19) (30 3 25) (6 5 31) (22 15 21)
(1 13 29) (10 11 28)  (26 12 27) (5 17 25) (21 9 33) (6 3 32) (22 16 19) (2 15 24) (18 8 31) (14 7 20) (30 4 23)
(1 14 30) (15 16 17)  (31 33 32) (2 6 26) (18 10 22) (11 8 5) (27 21 24) (3 12 9) (19 25 28) (7 4 13) (23 29 20)
(1 15 31) (14 16 33)  (30 17 32) (3 7 27) (19 11 23) (10 4 25) (26 9 20) (2 8 29) (18 13 24) (6 12 21) (22 5 28)
(1 16 32) (14 17 31)  (30 15 33) (4 8 28) (20 12 24) (6 13 19) (22 3 29) (10 5 23) (26 7 21) (2 9 27) (18 11 25)
(1 17 33) (14 15 32)  (30 16 31) (5 9 29) (21 13 25) (2 7 28) (18 12 23) (6 11 20) (22 4 27) (10 3 24) (26 8 19)
« Last Edit: April 15, 2011, 03:21:58 AM by Ian »


BG

  • Newbie
  • *
    • Posts: 5
Reply #9 on: April 15, 2011, 10:03:39 AM
Thanks Ian.  I am also curious about close solutions for the number of players between 22 and 33.

For instance, according to the schoolgirl problem, 18 does not meet the "perfect" requirements of 6n+3, but for a total of 18 players you can complete 8 rounds and only be missing one opponent.  Here is the table:

{"day 1: ", "ABC", "DEF", "GHI", "ahf", "dbi", "gec"}
{"day 2: ", "Abc", "Def", "Ghi", "aHF", "dBI", "gEC"}
{"day 3: ", "abC", "deF", "ghI", "AHf", "DBi", "GEc"}
{"day 4: ", "aBc", "dEf", "gHi", "AhF", "DbI", "GeC"}
{"day 5: ", "ADG", "BEH", "CFI", "aei", "bfg", "cdh"}
{"day 6: ", "Adg", "Beh", "Cfi", "aEI", "bFG", "cDH"}
{"day 7: ", "adG", "beH", "cfI", "AEi", "BFg", "CDh"}
{"day 8: ", "aDg", "bEh", "cFi", "AeI", "BfG", "CdH"}


The only pairs that don't play together are Aa, Bb, Cc, Dd, etc.  So I would consider that a very close solution. 

The same is true for 24 players.  You can complete 10 normal rounds and in the last round have 6 foursomes play to make everything "perfect".  See below:

{"day  1: ", "ABC", "DEF", "GHI", "JKL", "MNO", "PQR", "STU", "VWX"}
{"day  2: ", "JOT", "ESB", "API", "DML", "HCV", "QWN", "FKU", "GRX"}
{"day  3: ", "DVK", "SFO", "JQI", "EHL", "PTG", "WRC", "BMU", "ANX"}
{"day  4: ", "EGM", "FBV", "DWI", "SPL", "QKA", "RNT", "OHU", "JCX"}
{"day  5: ", "SAH", "BOG", "ERI", "FQL", "WMJ", "NCK", "VPU", "DTX"}
{"day  6: ", "FJP", "OVA", "SNI", "BWL", "RHD", "CTM", "GQU", "EKX"}
{"day  7: ", "BDQ", "VGJ", "FCI", "ORL", "NPE", "TKH", "AWU", "SMX"}
{"day  8: ", "OEW", "GAD", "BTI", "VNL", "CQS", "KMP", "JRU", "FHX"}
{"day  9: ", "VSR", "AJE", "OKI", "GCL", "TWF", "MHQ", "DNU", "BPX"}
{"day 10: ", "GFN", "JDS", "VMI", "ATL", "KRB", "HPW", "ECU", "OQX"}
{"day 11: ", "AFMR", "BNHJ", "CPOD", "EQVT", "GKSW", "IXUL", , }


So here is my question.  I'd like to create tables for an upcoming tournament.  I suspect that there will be between 22 and 33 players show up and I need to be prepared ahead of time to just fill in the blanks.  It appears that there are better solutions that exist for plugging in teams rather than just creating a bye.

For instance, on game day if I have 26 players show up, is there a better or closer solution that exists rather than using the 27 player table and just making one of the players a BYE?  The thing that helps me is it is unlikely that all rounds will be completed, so an odd round like I have shown above will not affect anything.  I know ahead of time that we will not complete all the rounds for a "perfect" solution.  What I am interested in is that we complete at least say 8 rounds with "perfect" threesomes and no repeats.
« Last Edit: November 25, 2019, 07:03:58 AM by Richard A. DeVenezias »


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1140
Reply #10 on: April 16, 2011, 08:58:36 AM
I do think the best solution will be found by deleting one player from the 27 player schedule.  This assumes that you are happy playing 8 threesomes and one pair.  The big advantage of course is that everybody is getting one round per day with nobody sitting out.  The alternative would be to play only the 8 threesomes, but with 2 players sitting out each round you must play the full 13 rounds in order that everyone, sits out exactly once, and so gets exactly 12 matches.


shaun hayward

  • Newbie
  • *
    • Posts: 3
Reply #11 on: April 20, 2011, 11:16:18 AM
Hello,

I am trying to find a solution for a 8 day match with 8 players! I would like it so tthat all players play together in a fourball an even amount of times I have tried many equations but it seems that there is always one who plays with  one other player 5 times and one who plays with another guy twice there must be a way please help!

Shaun


BG

  • Newbie
  • *
    • Posts: 5
Reply #12 on: April 20, 2011, 05:37:13 PM
Thanks for the reply Ian.  I'm really attacking a different kind of problem than was first proposed, but I find the threesome schedules interesting.  Especially the two schedules I mentioned that have "close" solutions.  Is it just coincidence that they are both multiples of 6 (18 players and 24 players).  That is why I thought there might be something close for 30 players.

I've also been studying latin squares and mutually orthogonal latin squares (MOLS) to try and find an answer.  From that study, I was able to find a perfect schedule for 39 players which does fit the 6n+3 requirement.  I have been looking for tables for MOLS of order 12 and 10, but it appears that they do not exist.


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1140
Reply #13 on: April 21, 2011, 09:59:19 AM
Hi Shaun,

If I understand correctly then the situation can not be even, some pairs of players will meet 3 times, while other pairs will meet 4 times.  For example:

(4 2 8 3)  (1 6 7 5)
(6 8 3 7)  (2 4 5 1)
(3 6 5 4)  (7 2 1 8)
(2 5 8 6)  (7 3 4 1)
(3 1 2 6)  (5 8 7 4)
(6 1 4 5)  (8 3 2 7)
(5 7 3 2)  (1 4 6 8)
(4 7 6 2)  (8 5 1 3)

Does that work for you?

Ian.


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1140
Reply #14 on: April 21, 2011, 10:07:25 AM
BG,

I think the multiples of 6 is just a coincidence.  It looks like the schedules you show above came from here, on the same page there is another resolvable group divisible design for 32 players in foursomes.

Complete sets of MOLS only exist if the order is prime, or an integer power of a prime number.  For 10 it's possible to have two orthogonal squares, for 12 it's possible to have 5 squares.

Ian.