2
$\begingroup$

Given a knock-out tournament with $2^n$ players, I am looking for a formula or algorithm to calculate the round player A will meet player B.

For the case $2^n=16$. Player 7 will meet player 8 in round 1, player 8 can meet player 9 in round 4 (the final).

How do I calculate the round in terms of n, A & B?

Thanks

  • 0
    no, they are numbered 1 (top) -16 (bottom) dependant on their position in the tournament ladder.2011-09-22

1 Answers 1

2

Let $(A-1)_2 = a_k a_{k-1} \ldots a_2 a_1$ and $(B-1)_2 = b_k b_{k-1} \ldots b_2 b_1$ be the binary representations of $A-1$ and $B-1$. Then the round in which $A$ and $B$ will meet is

$\max_i \ (a_i \neq b_i)$

Example: $A = 8$, $B = 9$. Then $(A-1)_2 = 7_2 = (0111)_2$ and $(B-1)_2 = (1000)_2$ so they will meet in the finals. If $B = 7$ then $(B-1)_2 = (0110)_2$ so they will meet in round $1$.