1
$\begingroup$

Suppose that you have six teams $x_0, x_1, x_2, x_3, x_4, x_5$. Can you schedule round-robin games between them so that if one game is played each day, the series of games can be completed in five weeks?

A naive attempt fails:

$$(x_0,x_1), (x_2, x_3), (x_4, x_5)$$ $$(x_0,x_2), (x_1, x_3) .. oops$$

Some care is needed to get this to work. A solution:

$$(x_0,x_3), (x_1, x_5), (x_2, x_4)$$ $$(x_1,x_4), (x_2, x_0), (x_3, x_5)$$ $$(x_2,x_5), (x_3, x_1), (x_4, x_6)$$ $$(x_0,x_1), (x_2, x_3), (x_4, x_5)$$ $$(x_0,x_5), (x_2, x_1), (x_4, x_3)$$

This solution certainly is not easy to generalize. Questions:

  1. Is this in fact always possible for an even number of teams?
  2. Is there a convenient algorithm for producing the schedule?
  3. Can this problem be easily expressed in terms of graph theory, combinatorics, or abstract algebra?
$\endgroup$
  • $\begingroup$ I described how the contract bridge players do a Howell movement, which solves this problem generically in this answer $\endgroup$ – Ross Millikan Oct 22 '13 at 14:26
-1
$\begingroup$

Let me explain the algorithm with 6 teams. You start

x1 vs x2

x3 vs x4

x5 vs x6

Then you keep x1 fixed and move the other teams (counter-)clockwise

x1 vs x4

x2 vs x6

x3 vs x5

and proceed doing this until every team has played against each other. For an odd number of teams you define x1 to be the bye.

x1 vs x6

x4 vs x5

x2 vs x3

then

x1 vs x5

x6 vs x3

x4 vs x2

and finally

x1 vs x3

x5 vs x2

x6 vs x4

$\endgroup$
  • 1
    $\begingroup$ Four teams is a pretty trivial case. This approach fails (or is unclear) for six teams. $\endgroup$ – Eric Wilson Oct 22 '13 at 13:20
  • $\begingroup$ Well I have done the 6 team case then. $\endgroup$ – Uwe Stroinski Oct 22 '13 at 13:23
  • 1
    $\begingroup$ As far as I understand your answer: this already fails for 6 teams: teams 3 and 4 would play each other again in the 3rd round. $\endgroup$ – Leen Droogendijk Oct 22 '13 at 13:26
  • $\begingroup$ After your edit the situation got worse: I fail to see any system in your description. I cannot even see how this would extrapolate to the next round, let alone how it would extrapolate to more teams. $\endgroup$ – Leen Droogendijk Oct 22 '13 at 13:33
  • $\begingroup$ I dont see your problem. Do you need a proof? $\endgroup$ – Uwe Stroinski Oct 22 '13 at 13:35
2
$\begingroup$

Here's an easy way for $2n \geq 6$.

Construct the regular polygon with $2n$ vertices. Label the vertices $x_1$ to $x_{2n}$. Take any edge that is not of the form $x_i, x_{i+n}$. Consider all edges that are parallel to it, and label them as 1 day of games. Rotate around the polygon and you are done.


For odd number of teams $2n+1 \geq5 $, show that you need $2n+1$ days. Repeat the above construction, taking note that you miss out 1 team each day.


If you read Ross's answer, you will see that this expresses the same idea.

$\endgroup$
1
$\begingroup$

Of course it's possible for any even number of teams.

Teams: $x_1, x_2, ...... x_{2n}$

Number of weeks: $2n-1$

What you're trying to do create a binary operation from teams to week numbers. It should look like that:

http://www.regentsprep.org/regents/math/algebra/an1/binarychart3.gif

The only difference is, the result of $x_1$ * $x_1$ is going to be $0$ or $2n$.

Let's build our operation, but first we have to know its properties:

  • No teams can play against itself. Then the diagonal must be all $0$, or something that is not a week number, then $\forall x_i, x_i*x_i = 0$

  • It should be abelian, that is $\forall \forall x_ix_j, x_i*x_j = x_j*x_i $ because if $x_i$ plays against $x_j$ in $n^{th}$ week, that is $x_j$ plays against $x_i$ in that week either. This means that your table should be symmetric around the diagonal.

  • We know that in each week, every team must play, and every team must play in every week. Then in every line and in every column, we have to see each week number, and we have to see them only once.

So what's the easiest way of building such a fixture. Really easy:

Make a table of all teams. For $2n$ teams, it should be $2n \,X \,2n$. Fill all the squares in the diagonal with 0. Then write the fixture of $x_1$ as $x_2, x_3, x_4 ....., x_n$, that is $x_1*x_2 = 1, x_1*x_3=2, ...... x_1*x_{2n}=2n-1$. Don't forget to add the symmetries to the column.

Edit: (See the history, I've corrected a critical mistake here)

Then when filling the second row, always follow the order except you're not allowed to write the number. Then fill the symmetries, and in the following step keep on following the order.

Simple example for $4$ teams.

enter image description here

Step by step example for $8$ teams:

enter image description here enter image description here

You'll notice that on actually those are diagonals from UpRight to DownLeft, except the $0$'s. When a $0$ cuts a diagonal of a number, then it takes place at the end of the row (and column of course). And, when a diagonal reaches the edge, then it continues from the first available square. But, as there are so many exceptions in the diagonal filling method, the other seemed easier to me.

$\endgroup$
1
$\begingroup$

Since you only ask for even $n$, you could use the fact that the complete graph $K_n$ is Hamilton decomposable for odd $n$ and decomposable into a perfect matching plus Hamiltonian cycles for even $n$. There is one single permutation that generates the Hamiltonian cycles. For even $n$ each Hamiltonian cycle gives you 2 rounds: one where player $2i$ plays player $2i+1$ and one where he plays player $2i-1$ (all $\pmod{2n}$). The perfect matching gives you the last round. The fact that this is a decomposition guarantees that every 'edge' is played. Details are here.

$\endgroup$
1
$\begingroup$

In terms of graph theory, what you are asking for is a decomposition of the complete graph on $n$ vertices into $n-1$ perfect matchings. The vertices are the competitors and the edges are the games. The edges in a perfect matching determine which games are played in a given week, so, if the edge $uv$ is in matching $i$, then $u$ and $v$ play against each other in week $i$. Perfect matchings are also called 1-factors, and a decomposition into perfect matchings is called a 1-factorization.

You could also say that it is a proper edge-colouring of the complete graph on $n$ vertices using $n-1$ colours. The edges in a colour class form a perfect matching. If the edges are coloured $1,2,...,n-1,$ then team $x$ plays team $y$ in week $i$ if the colour of $xy$ is $i$.

The construction that I was taught is to place vertices all vertices but one evenly around a circle, and place the other vertex, $u$ say, at the centre of the circle. For each vertex $v$ on the circle, form a matching from the edge $uv$ and all edges whose vertices are reflections of each other in the line through $u$ and $v$. Each matching can be obtained from the others by rotating around $u$.

You could also describe it in terms of modular arithmetic. Suppose that the vertices are $0,1,...,n-2,\infty$. Matching 0 has edges $\{\infty, 0\},\{1,n-2\},\{2,n-3\},\ldots$. All other matchings can be obtained by adding modulo $n-1$ to all vertices other than $\infty$. So

  • Matching 1 has edges $\{\infty, 1\},\{2,n-1\},\{3,n-2\},\ldots$
  • Matching 2 has edges $\{\infty, 2\},\{3,n\},\{4,n-1\},\ldots$
  • Matching 3 has edges $\{\infty, 3\},\{4,n+1\},\{5,n\},\ldots$
  • $\ldots$

This is equivalent to the construction that Uwe described elsewhere on this page.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.