Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
David Marcus
Posts:
40
From:
Somerville, Massachusetts
Registered:
12/4/04
|
|
round robin scheduling
Posted:
Jan 11, 2003 1:15 PM
|
|
I was asked for help with a tournament scheduling problem by the
Eightball Tasmania society:
http://www.eightballtasmania.org.au/
I don't know how to solve it, so I am asking for help. The question
is how to put players into small round-robin groups so that by the
end of the tournament, you've played a round robin of all the
players. To clarify, consider the following example.
Suppose there are 25 players and we want each player to play every
other player exactly once. We have 5 eightball tables, so we decide
to play the tournament in rounds. In each round, we send a group of
players to each table and have them play a round robin among
themselves. When we create a group, we do it so that none of the
players in the group have played each other in previous rounds. We
can play the entire tournament using 6 rounds using the following
schedule.
Round 1
Group 1: 1 2 3 4 5
Group 2: 6 7 8 9 10
Group 3: 11 12 13 14 15
Group 4: 16 17 18 19 20
Group 5: 21 22 23 24 25
Round 2
Group 1: 1 6 11 16 21
Group 2: 2 7 12 17 22
Group 3: 3 8 13 18 23
Group 4: 4 9 14 19 24
Group 5: 5 10 15 20 25
Round 3
Group 1: 1 10 14 18 22
Group 2: 2 6 15 19 23
Group 3: 3 7 11 20 24
Group 4: 4 8 12 16 25
Group 5: 5 9 13 17 21
Round 4
Group 1: 1 9 12 20 23
Group 2: 2 10 13 16 24
Group 3: 3 6 14 17 25
Group 4: 4 7 15 18 21
Group 5: 5 8 11 19 22
Round 4
Group 1: 1 8 15 17 24
Group 2: 2 9 11 18 25
Group 3: 3 10 12 19 21
Group 4: 4 6 13 20 22
Group 5: 5 7 14 16 23
Round 6
Group 1: 1 7 13 19 25
Group 2: 2 8 14 20 21
Group 3: 3 9 15 16 22
Group 4: 4 10 11 17 23
Group 5: 5 6 12 18 24
The problem is, what should the schedule be for other values of the
number of tables and players? They generally have either 5 or 6
tables, but they may have any number of players. Of course, the fewer
total rounds the better. And if all the groups in a round aren't the
same size, it is best if the groups are almost the same size so they
will all take about the same amount of time to play their matches.
--
David Marcus
|
|
|
|
