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?
HintConsider K=1 (2 players), the probability is 1.
Consider K=2 (4 players); first round can be in following ways:
1-2 | 3-4
1-3 | 2-4
1-4 | 2-3
They don't meet in finals in first case (of 3). Thus, for K=2, the probability that they meet is 2/3.
I assure you that this probability gets close to 1/2 for large K. Just notice that if 1 and 2 meet before final, they dont meet at final.
Answer
Solution
If you worked out conditional probability, that is fine. Here we present the combinatorial solution. Imagine the levels proceed in any random way such that player X and Y appear for final level. This can be imagined as N players getting partitioned into two groups of N/2 players each, with player X topping in first group and player Y in second. The best player of each partition reaches final. We only need to ensure that above partition separates player 1 from 2. The probability that a random partition separates 1 & 2 is (N/2) / (N-1) (how?)
Here is how: for creating a partition to separate them, we pick (N/2) people from N, wishing to take player 1, but not player 2.