Round Robin Tournament Schedule

Date: 03/31/2000 at 14:43:25
From: Blake Kinley
Subject: Scheduling sports competitions

What is the principle or formula I need to do this without using 
trial and error? I need to be able to create match schedules for up 
to 32 teams.

Here is a sample for 6 Teams that I worked out using the 
trial-and-error method.

Round 1:
Field A: Team 6 vs Team 1
Field B: Team 4 vs Team 3
Field C: Team 5 vs Team 2

Round 2:     Round 3:     Round 4:     Round 5:
A: 1-3       A: 2-4       A: 3-5       A: 6-5
B: 6-2       B: 1-5       B: 6-4       B: 3-2
C: 5-4       C: 6-3       C: 2-1       C: 4-1

Notice That each team plays on each field a maximum of twice 
(sometimes only once).

I need a method other than trial-and-error to create similar match 
schedules for 8 Teams on 4 Fields, 10 Teams on 5 Fields, and so on up 
to at least 32 Teams on 16 Fields.

HELP!

Date: 04/03/2000 at 13:52:26
From: Doctor TWE
Subject: Re: Scheduling sports competitions

Hi Blake - thanks for writing to Dr. Math.

Scheduling a round-robin tournament is not as easy as it looks. There 
is a systematic approach to scheduling that ensures that every team 
plays every other team once with the minimum amount of "idle time" (or 
byes). This method assumes that there are enough fields so that all 
the games in a round can be played simultaneously. The technique is 
sometimes referred to as the "polygon method." It has two variations, 
depending on whether the total number of teams is an even number or an 
odd number. I'll cover the odd case first.


POLYGON METHOD ROUND-ROBIN SCHDULING: ODD NUMBER OF TEAMS
---------------------------------------------------------
Let N = number of teams in the tournament. There will be N rounds 
(since each team will play every other team once, and will have 
exactly one idle round, or "bye"). I will use five teams (A, B, C, D, 
and E) in my example.

STEP 1: Draw a regular N-gon. (An N-gon is a polygon with N sides, for 
example a triangle, pentagon, heptagon, etc.) Each vertex represents 
one team, and can be labeled as such.

           A
           o
     E o       o B

         o   o
        D     C

STEP 2: Draw (N - 1)/2 line segments connecting the vertices such that:
   a) No vertex has more than one segment drawn to/from it, and
   b) No segment is a rotation or reflection of another segment.

One easy method to ensure that these conditions are met is to "stripe" 
the polygon. Draw the polygon such that the two lowest vertices are 
horizontal. Connect these two with a horizontal segment. Connect the 
two next lowest ones with another horizontal segment, etc. The top 
vertex will remain unconnected. (This is because there is an odd 
number of vertices.)

           A
           o
     E o-------o B

         o---o
        D     C

Each segment represents teams playing each other in the first round. 
In my example, team E plays team B and team D plays team C. Team A is 
idle in round one.

STEP 3: Rotate the polygon 1/(N - 1) of a circle. You can either rotate
the segments in the polygon (keeping the vertices fixed) or you can rotate
the vertices (keeping the segments fixed). I'm going to rotate the
vertices because it's easier to draw with ASCII graphics. The new segments
represent the match-ups for round two.

           E
           o
     D o-------o A

         o---o
        C     B

In my example, team D plays team A and team C plays team B in round 
two. Team E is idle.

STEP 4: Continue rotating the polygon until you return to your 
original position. Each rotation represents the match-ups of the next 
round. When you return to the original position, you don't record the 
match-ups, as they were already played in round one. For example:

Round three: C-E, B-A (D idle)

           D
           o
     C o-------o E

         o---o
        B     A

Round four: B-D, A-E (C idle)

           C
           o
     B o-------o D

         o---o
        A     E

Round five: A-C, E-D (B idle)

           B
           o
     A o-------o C

         o---o
        E     D

One more rotation would bring me back to my original position. Thus, 
my schedule looks like this:

     Round    Games:    Idle
     -----   --------   ----
       1     E-B, D-C    A
       2     D-A, C-B    E
       3     C-E, B-A    D
       4     B-D, A-E    C
       5     A-C, E-D    B

Why does this work? Requiring (N-1)/2 segments in step 2 ensures that 
there is only one idle team in each round, thus there will be the 
minimum number of rounds required. The restriction that no vertex has 
more than one segment drawn to/from it ensures that no team is 
scheduled for more than one game in each round. And the restriction 
that no segment is a rotation or reflection of another segment ensures 
that no match-up will be repeated in a future round.

A final note: For N > 6, the "striping" method is not the only way of 
drawing the segments for step 2,  but it is the easiest. Here are two 
ways of drawing them for a heptagon (N = 7):

            A                          A
            o                          o
      G o-------o B              G o  /    o B
                                    X       \
    F o-----------o C          F o/   \      o C
                                        \
         o-----o                    o     o
        E       D                  E       D

The "striping" method pairs G-B, F-C and E-D in round one, while the 
alternate method pairs A-F, G-D and B-C in round one. Each of these 
creates a valid schedule, they are not the same schedule with just 
some of the rounds switched.


POLYGON METHOD ROUND-ROBIN SCHDULING: EVEN NUMBER OF TEAMS
---------------------------------------------------------
Let N = number of teams in the tournament. There will be N - 1 rounds 
(since each team will play every other team once, and there will be no 
idle teams, or "byes"). I will use six teams (A, B, C, D, E and F) in 
my example.

STEP 1: Draw a regular (N-1)-gon. (for 4 teams draw a triangle, for 6 
teams draw a pentagon, for 8 teams draw a heptagon, etc.) Place a 
point in the center of the polygon. Each vertex and the center point 
represent one team, and can be labeled as such.

               A
               o

     E o               o B

               o F

           o       o
          D         C

STEP 2: Draw N/2 line segments connecting the vertices and the center 
point such that:
   a) No vertex (nor the center point) has more than one segment drawn 
      to/from it, and
   b) No segment is a rotation or reflection of another segment.

This is essentially the same as the odd case, but the "idle" team 
plays the "center" team.

"Striping" still works, but the top vertex must be connected to the 
center point. For example

               A
               o
               |
     E o-------+-------o B
               |
               o F

           o-------o
          D         C

Each segment represents teams playing each other in the first round. 
In my example, team E plays team B, team D plays team C, and team A 
plays team F in round one.

STEP 3: Rotate the polygon 1/Nth of a circle (i.e. one vertex point). 
You can either rotate the segments in the polygon (keeping the 
vertices fixed) or you can rotate the vertices (keeping the segments 
fixed). I'm going to rotate the vertices because it's easier to draw 
with ASCII graphics. The new segments represent the match-ups for 
round two.

               E
               o
               |
     D o-------+-------o A
               |
               o F

           o-------o
          C         B

In my example, team D plays team A, Team C plays team B, and team E 
plays team F in round two.

STEP 4: Continue rotating the polygon until you return to your 
original position. Each rotation represents the match-ups of the next 
round. When you return to the original position, you don't record the 
match-ups, as they were already played in round one. For example:

Round three: C-E, B-A, D-F

               D
               o
               |
     C o-------+-------o B
               |
               o F

           o-------o
          B         A

Round four: B-D, A-E, C-F

               C
               o
               |
     B o-------+-------o D
               |
               o F

           o-------o
          A         E

Round five: A-C, E-D, B-F

               B
               o
               |
     A o-------+-------o C
               |
               o F

           o-------o
          E         D

One more rotation would bring me back to my original position. Thus, 
my schedule looks like this:

     Round       Games:
     -----   -------------
       1     E-B, D-C, A-F
       2     D-A, C-B, E-F
       3     C-E, B-A, D-F
       4     B-D, A-E, C-F
       5     A-C, E-D, B-F

You also mentioned restricting the number of fields in play. This can 
be tricky. Usually, you can start the games for round one in timeslot 
one, play the remaining round one games in timeslot two, and find 
games from round two that don't involve teams already playing in 
timeslot two, etc. If there are less than N/4 fields, the round one 
games will fill timeslots one and two, and spill into timeslot three, 
etc.

I hope this helps. If you have any more questions, write back.

- Doctor TWE, The Math Forum
  http://mathforum.org/dr.math/