返回题库

淘汰赛决赛相遇概率

Chess Tournament

专题
Strategy / 策略
难度
L4

题目详情

国际象棋锦标赛共有 2n2^n 名选手，实力严格排序：1（最强）> 2 > ... > 2n2^n（最弱）。

采用单败淘汰赛，共 nn 轮。除决赛外，每轮对阵随机。

两人相遇时更强者必胜。

问：#1 与 #2 在决赛相遇的概率是多少？

A chess tournament has 2n2^n players labeled by skill: 1 (best) > 2 > … > 2n2^n (worst). It’s a single-elimination (knockout) format, so there are nn rounds. Except for the final, matchups each round are random. When two players meet, the better one always wins. What is the probability that #1 and #2 meet in the final?

解析

答案为

2n−12n−1.\frac{2^{n-1}}{2^n-1}.

等价解释：把 #2 随机放到除 #1 之外的 2n−12^n-1 个位置上。要在决赛相遇，#2 必须落在对阵表的另一半区（与 #1 不同半区）。另一半区共有 2n−12^{n-1} 个位置，因此概率为 2n−12n−1\frac{2^{n-1}}{2^n-1}。

Original Explanation

  • Method 1 (Conditional Probability)
    They must avoid meeting in each of the first n−1n-1 rounds. In round ii, there are 2 n−i+12^{\,n-i+1} players left, so the probability that #1 does not meet #2 in that round is  2 n−i+1−2  2 n−i+1−1 .\frac{\,2^{\,n-i+1} - 2\,}{\,2^{\,n-i+1} - 1\,}. Multiplying these for i=1i=1 to n−1n-1 yields  2 n−1  2n−1 .\frac{\,2^{\,n-1}\,}{\,2^n - 1\,}.

  • Method 2 (Separate Brackets)
    #1 is guaranteed to win each match and reach the final. For #2 to meet #1 there, #2 must be placed in the other half of the bracket. The probability that #2 is in the opposite bracket is  2 n−1  2n−1 .\frac{\,2^{\,n-1}\,}{\,2^n - 1\,}.