4

Suppose I start with $N$ teams ($N$ is even) which are randomly paired with each other in the first round. $\frac N2$ teams progress into the next round. I want this process to repeat itself until one team remains. But this is problematic if we have an odd number of teams remaining after a round concludes. My questions:

  • If the number of teams is odd after a round concludes, how should I adjust the number of teams? Obviously I could just eliminate an extra team, but is there a more efficient way to handle this so I don't have to keep eliminating teams after each round? I suppose I would have to try and get $N$ onto the pathway $(1,2,4,8,16,\dots)$?

  • Given the pruning approach I adopt, how do I derive the number of rounds in the tournament?

rjt90
  • 113

2 Answers2

5

Suppose $2^{m-1}< N \le 2^m$. The usual way that tournaments handle this is by giving teams byes, i.e. they automatically continue to the next round. This is equivalent to assuming that there are $2^m$ teams, with $N$ real teams and $2^m-N$ imaginary teams that always lose when they play (byes). The number of rounds will be exactly $m$ in this approach, with the total number of teams (real and imaginary), being divided by 2 at each step.

The proposed approach of eliminating teams even when they won the previous round, would prove unpopular with members of that team. :-)

vadim123
  • 82,796
  • Thanks - very helpful and answers the question. Incidentally, the reason why I proposed elimination is because the game I am modelling involves death/survival (!), but this is simply the flipside of the problem. – rjt90 Jul 28 '13 at 16:15
  • Usually the first round is arranged so no two imaginary teams play each other. There are then no byes after the first round and the number of games a team must win differs by at most one from any other team. – Ross Millikan Jul 28 '13 at 16:40
3

There is a whole boatload of mathematical literature about tournaments, going back, I believe, to Charles Lutwidge Dodgson (better known as Lewis Carroll). You will probably find most of it, these days, under the heading of "computer science" where it is a key concept of "sorting". As such, you may be better off asking this question over on the CS StackExchange site. The minimal number of games is actually only known for a very limited number of tournament sizes.

Edit: I knew I was forgetting something. Although sorting relates to tournaments, selection is more directly relevant. Selection algorithms answer questions like "Which team is best?" "What are the top two teams, in order?" "What team is in the middle?". Look up, for example "median-of-medians algorithm".

dfeuer
  • 9,069