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

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

-
How are the players numbered? In accordance with their seeding? – Dilip Sarwate Sep 22 '11 at 14:39
no, they are numbered 1 (top) -16 (bottom) dependant on their position in the tournament ladder. – Martin Sep 22 '11 at 14:48

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