Round-robin scheduling
Problem
Note: for this problem it's handy to have colour pens ready!
A round-robin tournament is one in which every player plays against everyone else once. For example, with 3 players, we will have 3 matches: A-B, B-C, C-A. How many matches are needed for 4 players? 5 players? N players?
If we can schedule two matches in the same time slot (round), how many rounds will it take for a 3-player round-robin tournament? 4-player tournament? 5-player tournament?
Now that we have played with the scheduling problem for a bit, let's think of a graphical way to represent the problem. If we represent a player by a point and each match as a line between two points, the graph representing all the matches in a 3-player tournamnet will be the triangle ABC. The graph representing a 4-player tournament will be the quadrilateral ABCD together with diagonal
lines AC and BD. Can you draw the graph for 5-player tournament? 6-player tournament?
If we schedule two matches in a round, how can we show in the same graph which two pairs of players are playing in the same round (hint: if you have only been using one pen, now is the time to use another colour!) Try this for tournaments with 4, 5 and 6 players. Be careful with the 6-player tournament! Remember that a particular pair of players should only play each other once, so if the
line connecting the same two players is coloured more than once then we are in trouble. Try again if it doesn't work the first time. It can be done, but the solution is surprising tricky to find if we start drawing the graph as a hexagon with all vertices connected to each other.
There is a nice trick, which works for all tournaments with an even number of players. We will illustrate this with a 6-player tournament. Instead of drawing a hexagon, draw a pentagon with one extra vertex in the center of the graph. Connect one vertex of the pentagon to the vertex at the center and connect the remaining vertices with horizontal lines. For the next round, use a different
coloured pen to do the same connecting but with each vertex of the pentagon rotated into the neighbouring vertex. Do this until all lines are coloured. We end up with a fully-connected graph with no line coloured twice! Why does this work? Can we use this trick for a 5-player tournament?
We can also include information about home/away game by an arrowed line. For tournaments with 4, 5, 6 players, how many games are played home or away by each player? Can you find a fair scheduling such that no team plays all games at home nor away?