We are designing a tournament for a game such as soccer (football) or chess. The tournament is "round robin." By "round robin," we mean that every team gets to play against each other team exactly once. For example, if you are playing, and there are 8 other teams, then you will play exactly 8 matches before the tournament is over.
A single "match" is played with 2 teams competing against each other. For example, (team 3 against team 9) is a single match. Formally, a match is a set of two integers, such as {3, 9}.
The tournament is divided into rounds. All teams who are scheduled to play during the current round play simultaneously. If team 2 is playing team 5 during round 10, then team 2 cannot simultaneously play against team 3 during the same round. In different notation, if {2, 5} ∈ R10 then {2, 3} ∉ R10. In general, no round is allowed to contain the same team more than once.
Formally, a round is a set of matches. For example, $R = \{\{1, 2\}, \{3, 5\}, \{4, 6\}\}$ is a round. A valid round $R$ is a round such that for every two distinct matches, M1 and M2, in $R$, $M1$ ∩ $M2$ is the empty set. This captures the idea that no round is allowed to contain the same team more than once.
For some natural number, $n$, the tournament has:
- $2*n$ teams
- $(2*n-1)$ rounds
- $n$ matches per round.
The algorithm we seek, for any even number of teams, will output a a description of which matches to have in each round.
For example, for 6 teams, the algorithm output might be:
round 1: {1, 2}, {3, 5}, {4, 6}
round 2: {1, 3}, {2, 4}, {5, 6}
round 3: {1, 4}, {2, 5}, {3, 6}
round 4: {1, 5}, {2, 6}, {3, 4}
round 5: {1, 6}, {2, 3}, {4, 5}
Note that every team plays at most once per round, and that every team plays every opposing team exactly once before the tournament is over.
