国际象棋锦标赛

Chess Tournament

专题: Probability / 概率
难度: L4
来源: Brainstellar

题目详情

有 $N=2^K$ 名棋手，实力严格排序 $P_1>P_2>\cdots>P_N$ ，且比赛中更强者一定获胜。

采用单败淘汰赛，所有对阵/分组等价于随机生成一张淘汰赛对阵表。

问： $P_1$ 与 $P_2$ 在决赛相遇的概率是多少？

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

Hint

if two players meet before the final, they don't meet at the final.

解析

答案为

\frac{N}{2(N-1)}.

等价观点：随机把 $P_2$ 放到 $P_1$ 之外的 $N-1$ 个位置中。它与 $P_1$ 处于同一半区（从而在决赛前相遇）的概率为 $\frac{N/2-1}{N-1}$ ，处于不同半区（从而决赛相遇）的概率为

1-\frac{\frac{N}{2}-1}{N-1}=\frac{N}{2(N-1)}.

Original Explanation

$\dfrac{N}{2(N-1)}$

Solution

Consider $K=1, N=2$ , the probability is 1.

Consider $K=2, N=4$ ; the first round can be in the following ways:

$(P_1 \times P_2 ) \times ( P_3 \times P_4 )$
$(P_1 \times P_3 ) \times ( P_2 \times P_4 )$
$(P_1 \times P_4 ) \times ( P_2 \times P_3 )$

They don't meet in finals in the first case (out of a total of three). Thus, for $K=2, N=4$ , the probability that they meet is $2/3$ .

Assume that instead of forming random pairs at each level, we have already constructed a "tournament tree", which is a binary tree. At the bottom of this structure, we have the initial $N$ players. Each node represents the match between the two children (players), and the value of each node is the player who won that match. The value of the top-level root node is the overall winner of the tournament.

tree

With this image, we can see the whole tournament is deterministic and only depends on the initial arrangement of players (at the bottom level). We also notice that the two players who reach the final level are the best players of the left half of the tree and the right of the tree (respectively).

Imagine $N$ players getting partitioned into two groups of $N/2$ players each, with player $P_1$ topping in the first group and player $P_2$ in the second. The best player of each partition reaches the final. The probability that a random partition separates player $P_1$ from $P_2$ is $\dfrac{(N/2)}{(N-1)}$

Here's how: There are $N$ empty slots in a sequence at the bottom layer of the tournament tree. We can start assigning players from $P_1$ . Suppose $P_1$ is assigned to a slot in the first half. For $P_2$ , there are total $N-1$ slots remaining, and $N/2$ are in a new group (that does not contain $P_1$ ). Hence, there are $(N/2)$ favorable choices and $N-1$ total choices.

Hence the probability is $\dfrac{N}{2(N-1)}$

Note: The question says that we are forming random pairs at each level. But that is equivalent to retroactively constructing the bottom-layer of the tournament tree, in any desirable fashion.

For example, consider at the $i$ th level, we randomly decide to match $P_j$ with $P_k$ , even though they were not siblings in the tree at that level. That's fine, we can modify the tree such that now $P_j$ and $P_k$ are siblings, while keeping the entire branch below each of those nodes intact.