Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.