返回题库

2n2^n 人随机单败淘汰：两人从不相遇概率

2n2^{n} players

专题
Strategy / 策略
难度
L4

题目详情

Consider 2n2^{n} players of equal skill 28^{28} playing a game where the players are paired off against each other at random. The 2n−12^{n - 1} winners are again paired off randomly, and so on until a single winner remains. Find the probability that two contestants never play each other.

解析

设两位选手为 A、B。由于每轮随机配对且选手水平相同，他们在某轮相遇当且仅当两人都存活到该轮并被配到一起。

可用对称性计算相遇概率：对固定的 A，在整个比赛中他与某个特定对手交手的概率对所有对手相同。并且 A 期望打的场数为

E[NA]=∑k=0n−1P(A赢前 k 场)=∑k=0n−12−k=2(1−2−n).\mathbb{E}[N_A]=\sum_{k=0}^{n-1}\mathbb{P}(A\text{赢前 }k\text{ 场})=\sum_{k=0}^{n-1}2^{-k}=2\left(1-2^{-n}\right).

令 pp 为 A 与某个固定对手（如 B）相遇的概率，则

E[NA]=(2n−1)p⇒p=2(1−2−n)2n−1=21−n.\mathbb{E}[N_A]=(2^n-1)p\Rightarrow p=\frac{2(1-2^{-n})}{2^n-1}=2^{1-n}.

因此两人从不相遇的概率为

1−21−n.\boxed{1-2^{1-n}}.