3
$\begingroup$

Imagine there are 12 teams, numbered 1 through 12. There are 10 games those teams can compete in, with two teams needed per game. There are 10 rounds, and it is important that after the 10 rounds are over each team has played each game exactly once. Ideally each team plays a different team each round.

This seems like a simple problem but how can I solve this? This seems like an optimization problem, but I'm having difficulty making a correct grouping. I've tried for a couple hours but each time I think I've come up with an algorithm I eventually run into a problem.

Tom

$\endgroup$
  • $\begingroup$ please show some of your steps $\endgroup$ – Hailey Jun 28 '16 at 9:13
  • $\begingroup$ I'd be happy to add the excel sheet with my latest tries, however I don't get past the 5th round without having problems $\endgroup$ – Tom Schoehuijs Jun 28 '16 at 9:25
1
$\begingroup$

You could proceed in two steps:

  • First, find the different matches over a set of runs:

In terms of graph theory, you are looking for 10 distinct matchings with maximum cardinality in which vertices represent teams, and edges represent games between teams. In other words you want to color all the edges of a complete graphe with 12 vertices, with 10 colors, such that two adjacent edges have different colors.

This is actually not difficult to achieve: place vertex $12$ in the center and the $11$ other teams around in circle. You can then color vertices $1$ and $12$, $2$ and $11$, $3$ and $10$, $4$ and $9$, $5$ and $8$, $6$ and $7$: this is your round $1$.

For round $2$, proceed as follows: $2$ and $12$, $1$ and $3$, $4$ and $11$, $5$ and $10$, $6$ and $9$, $7$ and $8$. Round $3$: $12$ and $3$, $2$ and $4$, $1$ and $5$, $6$ and $11$, $7$ and $10$, $8$ and $9$.

See the pattern ? On the graph, it is just a repetition of day $1$, after a clockwise rotation of the matching (do the drawing, you will see it and figure out the next rounds).

  • Second, assign the matches to games:

A match is defined by a tuple $m=(i,j,r)$ (teams $i$ and $j$ play together at round $r$). So let $x_{m}^{g}$ be a binary variable that equals $1$ if and only if match $m\in M$ is assigned game $g\in G$. Let $M_r\subset M$ denote the set of matches of round $r$, and $M_i\subset M$ the set of matches with team $i$. You can maximize or minimize an arbitrary function subject to:

$$ \sum_{g}x_{m}^{g}=1\quad \forall m \\ \sum_{m\in M_r}x_{m}^{g}\le 1\quad \forall g \;\forall r\\ \sum_{m\in M_i}x_{m}^{g} = 1\quad \forall g \;\forall i\\ x_{m}^{g} \in \{0,1\} $$

The first constraint makes sure that all matches have a game, the second one makes sure a game is not given to more than one pair of teams at each round, and the last constraint imposes each team to play every game over the different runs.

According to my numerical tests, here are two different solutions:

enter image description here

enter image description here

$\endgroup$
  • $\begingroup$ Thanks for helping! The problem isn't really in finding matches (team 1 vs team 7, etc), it's in then assigning these matches to games, so that each team has played each game after 10 rounds. Will your method work for that? $\endgroup$ – Tom Schoehuijs Jun 28 '16 at 11:30
  • $\begingroup$ Can a same game be played simultaneously by two different pairs of teams? $\endgroup$ – Kuifje Jun 28 '16 at 13:35
  • $\begingroup$ Nope, they can't $\endgroup$ – Tom Schoehuijs Jun 28 '16 at 14:01
  • $\begingroup$ This is not an easy problem (but its a nice one!). I am not sure if there is a way around this without integer programming. In all cases I have provided 2 different solutions. There are probably more. $\endgroup$ – Kuifje Jun 29 '16 at 15:44
  • $\begingroup$ Brilliant! Thanks! $\endgroup$ – Tom Schoehuijs Jun 29 '16 at 20:50

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.