Question

A chess tournament has k levels and 2^k players with skills 1 > 2 > ... >2^k. At each level, random pairs are formed and one person from each pair proceeds to next level. When two opponents play, the one with better skills always wins. What is the probability that players 1 and 2 will meet in the final level?

Answer 1

Explanation:

One way to view this is as a branching tournament bracket (or a complete binary tree if you prefer) and to place the competitors randomly at each starting point, or each leaf node. Then, player 2 must be placed on the opposite side of the bracket as player 1 in order to meet in the final. We decide where player 1 gets put first. Then, that leaves 2n−1 places for player 2 to go. But, he must go in the other half to make it to the final, and that means 12(2n)=2n−1 possible places, giving us the solution 2n−12n−1. Intuitively, for a large bracket, we would expect him to reach the final about half the time, and indeed the value is approximately 1/2 for large n