Determining the round players will meet in a knock-out tournament

Question

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

Answer 1

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$.