Round Robin Tournament Scheduling

Help for 10 teams, and 10 games

lexus500 · 9 · 3808

lexus500

  • Newbie
  • *
    • Posts: 3
on: December 08, 2009, 02:02:01 PM
Hi

I am running a camp for 10 teams.

There are 5 different game stations (Game A, B, C, D, E) on day 1,
and another 5 different game stations (Game F, G, H, I, J) on day 2.

All the games on the two days are run concurrently.
Meaning, for day 1, Games A, B, C, D, E will be run at the same time.

Teams are to visit each game station to challenge another team - ie 2 teams will be at 1 game station.

Each game master will conduct each game a total of 5 times - at 1pm, 2pm, 3pm, 4pm, 5pm.
So for eg, at
1pm ( team 1 vs team 2 );  
2pm ( team 3 vs team 4 );
3pm ( team 5 vs team 6 );
4pm ( team 7 vs team 8 );
5pm ( team 9 vs team 10 )..

It will be the same for day 2.

My objective is:
- Each team must play EVERY game ONCE only. (Eg, Team 1 must play Game A, and can only play it once.)
- To try to make each team compete with everyone else at least once*.


Also, what about if I have 8 teams, and 4 game stations (day 1), 4 game stations (day 2)?
Or, 12 teams, and 6 game stations (day 1), 6 game stations (day 2)?
Or, 14 teams, and 7 game stations (day 1), 7 game stations (day 2)?


*PS:
In this arrangement, there will be a total of 50 rounds of games being played.
To make a round robin, only 45 rounds are needed.
So, in the extra (50 - 45 = 5) rounds, some teams will compete with the same team twice.
It does not matter which teams compete with same team twice.
« Last Edit: May 23, 2018, 02:47:21 AM by Richard A. DeVenezia »


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1130
Reply #1 on: December 10, 2009, 05:47:32 AM
There is a special form of balanced round-robin called a partitioned balanced tournament design which will meet your needs.  For 10 teams a solution is given below:

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


The properties of the PBTD are that each team appears once or twice in each column, the two teams who only appear once in a column, the so called deficient pairs, all occur in the middle round.  Finally the matches in rounds 1 to 5 taken from any column contain all the teams exactly once.  Given these properties it must also be the case that rounds 5 to 9 from any column also contain all the teams exactly once.  So this gives you the schedule that you want: use rounds 1 to 5 for day 1, and then rounds 5 to 9 for day 2, as round 5 is used twice it might be a good idea to rearrange the order of play so that it is used at the start of day 1 and at the end of day 2 - that way the repeated matches are all as far apart as possible.

Below I have pasted similar scedule for 12 and 14 teams.  Unfortunately no PBTD exists for 8 teams.

Hope that helps.


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

(G D) (E M) (L A) (J N) (C H) (I F) (K B)
(I M) (L N) (K J) (B C) (F G) (D A) (E H)
(L C) (K F) (H I) (D E) (B M) (G N) (J A)
(J E) (B I) (C N) (A F) (D K) (H M) (L G)
(N F) (A H) (G B) (M K) (E L) (J C) (I D)
(K H) (J G) (D M) (I L) (A N) (E B) (F C)
(A B) (C D) (E F) (G H) (I J) (K L) (M N)
(D J) (I E) (N K) (C M) (L B) (A G) (H F)
(C I) (F J) (M L) (N D) (K A) (B H) (G E)
(H N) (G K) (B D) (L J) (M F) (C E) (A I)
(M G) (H L) (A C) (K I) (N E) (F D) (B J)
(E K) (M A) (J H) (F B) (G C) (N I) (D L)
(F L) (N B) (I G) (E A) (H D) (M J) (C K)
« Last Edit: December 10, 2009, 05:52:09 AM by Ian »


lexus500

  • Newbie
  • *
    • Posts: 3
Reply #2 on: December 11, 2009, 08:06:33 PM
Hi Ian,

Thks sooo much for your help.

May I know if there is any formula to doing this scheduling? Or is it some computer program? I'm interested to find out how you did it!!


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1130
Reply #3 on: December 12, 2009, 03:05:43 AM
Lexus,

Thanks for your kind words.  I have tried to find these type of schedules using a computer program, but with very little success, I can find the 10 team solution but none of the larger schedules.   What you need is some combinatorial mathematics,  for example this masters thesis by Shane Bauman, gives some examples of the methods that can be used to construct schedules.

Ian.
« Last Edit: December 12, 2009, 03:09:22 AM by Ian »


lexus500

  • Newbie
  • *
    • Posts: 3
Reply #4 on: January 11, 2010, 12:59:50 PM
Hi Ian,

I've spent about a month trying to digest the masters thesis by Shane Bauman that you sent on PBTD. I think I'm only able to grasp probably 40% of it, as I'm very new to this area of mathematics.

May I ask how you managed to construct the schedule for 10, 12 and 14 teams? Or, please advise me if there is any website where I can find this information. I am currently trying to construct a schedule for 16 teams, 18 teams, 20 teams and 22 teams.

Thks a million!!


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1130
Reply #5 on: January 12, 2010, 04:00:41 AM
I think the thesis has been my main source, although I have seen the 10 team schedule published elsewhere.  Below are schedules for 16 and 20 teams that I made some time ago now.   As far as I am aware the 18 team schedule is still an open mathematical problem, so I can't help you there.  When I have more time, I will look into making a 22  team schedule.


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

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


PS. Just checked the thesis again, and I see that the 22 team schedule is not constructed - a second open problem.
« Last Edit: May 23, 2018, 02:50:25 AM by Richard A. DeVenezia »


Strike_Ump

  • Newbie
  • *
    • Posts: 6
Reply #6 on: April 01, 2011, 01:00:59 PM
That thesis is way over my head haha. This is a good set up for a ten teamer though.
You're Out!


adrianhgh

  • Newbie
  • *
    • Posts: 3
Reply #7 on: September 25, 2012, 03:13:29 AM
Hi Ian, is there a similar schedules for 6 and 8 teams?
If not, is it possible to provide me with a "best" schedule?


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1130
Reply #8 on: September 27, 2012, 03:22:18 AM
These schedules do not exist and it is even hard to come close.  For 6 teams it is possible to write down the first 3 rounds:

(A D) (B E) (C F)
(B F) (C D) (A E)
(C E) (A F) (B D)


but then it is impossible to complete it, so your best solution is to use the standard balanced schedule.  Similarly for 8 teams the first 4 rounds are possible:

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


but this time the schedule can be completed, however the balance at each of the four venues is lost:

(A C) (B D) (E H) (F G)
(E F) (G H) (C D) (A B)
(E H) (A D) (B C) (E G)
« Last Edit: September 27, 2012, 03:25:01 AM by Ian »