1

I need to prove by induction the theorem that says we can construct a round robin tournament:

Given a tournament with $2^k$ teams. We label the teams $t_1, t_2, ..., t_{2^k}$. It is possible to construct $2^k -1$ rounds of $2^{k-1}$ games where each team plays with each other team only once.

I have come up with the base case:

For $k=1$, we have 2 teams. There will be $2^1 - 1 = 1$ round, witg $2^{1-1} = 1$ game. This game is $\{t_1, t_2\}$.

However, I can't come up with the inductive step. I do know the algorithm, described here.

gberger
  • 123

1 Answers1

1

Now you assume you have a tournament schedule with $2^k$ teams with $2^k-1$ roundsand show how to make a tournament with $2^{k+1}$ teams in $2^{k+1}-1$ rounds. Take your $2^{k+1}$ teams, split them into two groups of $2^k$ and play the tournament that you know exists. Then play each team in one group against each team in the other group. You can just start with $j vs j+2^k$ and rotate the upper teams around the lower teams.

Ross Millikan
  • 374,822
  • Thanks. But this means I'd have to use a different algorithm than the one described on Wikipedia, right? – gberger Apr 22 '14 at 19:44
  • 1
    That is correct. The Wikipedia approach works for any number of teams. Since you asked about $2^k$, I assumed all tournaments you were interested in were powers of $2$ and you wanted induction with a factor of two, not adding one more team. There are many ways to structure these tournaments. – Ross Millikan Apr 22 '14 at 19:50