淘汰赛夺冠的概率

KeyTo9_Fans

对于某种棋类比赛（如象棋、围棋等），某个人的实力一般可以用一个数值来衡量，例如：$100$。

如果两个人的实力分别是$a$和$b$，那么他们在一局比赛中，

实力为$a$的人的获胜概率是$a/(a+b)$，

实力为$b$的人的获胜概率是$b/(a+b)$。

为了简单起见，这里并不考虑和棋、无胜负、比赛中断、违规等特殊结果。

例如：实力分别为$1$和$100$的人进行一局比赛，

实力为$1$的人的获胜概率就是$1/101$，

实力为$100$的人的获胜概率就是$100/101$。

现在有$16$位参赛选手，实力分别是$1$、$10$、$100$、$1000$、……、$10^15$，

他们要通过$4$场淘汰赛（即$16$强赛、$8$强赛、半决赛、决赛）争夺冠军，

每场比赛都是一局定胜负，胜者晋级下一场比赛，败者被淘汰。

问：

$1$、实力最强的选手在哪种分组方案下的夺冠概率最大？最大的夺冠概率是多少？

$2$、实力最强的选手在哪种分组方案下的夺冠概率最小？最小的夺冠概率是多少？

$3$、如果抽签决定分组（抽到每种分组方案的概率均等），那么实力最强的选手的夺冠概率是多少？

$4$、当淘汰赛的场数为$n$，参赛选手的数量为$2^n$，实力分别是$1$、$10$、……、$10^{2^n-1}$时，上述$3$个问题的答案是否有极限？如果有，极限分别是多少？

$5$、设想我国共有$2^n$名选手，我们要通过国内的选拔赛选出$1$名最优秀的选手参加国际赛事。选拔赛前我们只知道选手们的实力呈等比分布，但不知道任何选手的实力高低。由于时间、场地、资金等限制，选拔赛能进行的总局数有限，仅为$(2^n+c)$局，$c$是一个常数。我们希望选拔赛选出来的选手的实力的期望值最大，问应该如何安排这$(2^n+c)$局比赛？最大的期望值是多少？

whbns

1.要想最大化最强选手A的夺冠概率，我觉得应该把较弱的选手（排名10-16）和A分到同一个半区，较强的选手（排名2-9）分到另一个半区。总的来说就是优先给A分配较弱的对手，而给其主要对手分配较强的对手。有意思的是，这时候排名2-9的半区正好转化成了问题2，也就是最小化排名第2的人进入决赛的概率。而A的这个半区可以递归问题1，最终也都会归到问题2上。
2.与问题1相反，要最小化最强选手夺冠概率，就要优先给他较强的对手，而给其主要竞争对手较弱的对手。
所以我觉得分组应该是这样的：（A表示实例最强的，其他选手用实力排名表示）
问题1：{[(A,16),(14,15)],[(10,11),(12,13)]},{[(2,3),(4,9)],[(5,8),(6,7)]}
问题2：{[(A,2),(3,16)],[(4,15),(13,14)]},{[(5,12),(10,11)],[(6,7),(8,9)]}

wayne

这个题目比较有意思。
这16个选手的实力值如果不是 等比分布。对于问题一的最终的分组方案是不是有可能会变化。 即，最强选手概率最大夺冠的分组方案，是否依赖于这16个人实力值的具体分布情况？
==============

先算一下16强最终决出冠军的分组方案个数，有 $\frac{16!}{(2!)^8 8!} * \frac{8!}{(2!)^4 4!}  * \frac{4!}{(2!)^2 2!}  = 2027025 *105 *3 = 638512875 $，这个数目并不大，似乎可以枚举一下。

BeerRabbit

wayne 发表于 2016-8-13 10:15
这个题目比较有意思。
这16个选手的实力值如果不是 等比分布。对于问题一的最终的分组方案是不是有可能会 ...

都6E了还不大………………

KeyTo9_Fans

$638512875$种分组方案不算太多，编个程序运行，很快就枚举完了。

使用long double数据类型计算概率，得到夺冠概率最小的分组方案有$12$种：

1 2 3 15 4 16 13 14 5 12 10 11 6 7 8 9
1 2 3 16 4 15 13 14 5 12 10 11 6 7 8 9
1 2 4 15 3 16 13 14 5 12 10 11 6 7 8 9
1 2 4 16 3 15 13 14 5 12 10 11 6 7 8 9
1 3 2 15 4 16 13 14 5 12 10 11 6 7 8 9
1 3 2 16 4 15 13 14 5 12 10 11 6 7 8 9
1 3 4 15 2 16 13 14 5 12 10 11 6 7 8 9
1 3 4 16 2 15 13 14 5 12 10 11 6 7 8 9
1 4 2 15 3 16 13 14 5 12 10 11 6 7 8 9
1 4 2 16 3 15 13 14 5 12 10 11 6 7 8 9
1 4 3 15 2 16 13 14 5 12 10 11 6 7 8 9
1 4 3 16 2 15 13 14 5 12 10 11 6 7 8 9

以上分组，$1$表示实力最强。

$12$种分组方案的夺冠概率皆为$0.89910761028348250111$。

由于long double的精度只有$19$位，

目前还不知道这$12$种分组的夺冠概率是否并列最小，

需要通过更高精度的计算才能得知。

而夺冠概率最大的分组方案只有$1$种：

1 16 13 14 8 9 10 11 2 3 4 15 5 12 6 7

概率为$0.91742227461217951847$。

而这个分组：

1 16 14 15 10 11 12 13 2 3 4 9 5 8 6 7

夺冠概率只有$0.91742227255220405326$。

至于为什么【把实力较强的$8$和$9$替换掉实力较弱的$12$和$15$后放到$1$所在的半区】反而会增大$1$的夺冠概率，

目前尚不清楚，

看来最佳的分组方案没有想象的那么简单。

所有分组的平均夺冠概率为$0.90550329604277566248$，

与抽签实战模拟$95613353984$次得到的夺冠比率$0.9055028383533962$相近。

whbns

KeyTo9_Fans 发表于 2016-8-17 08:42
$638512875$种分组方案不算太多，编个程序运行，很快就枚举完了。

使用long double数据类型计算概率，得 ...

把较弱的选手换到另一个半区可以降低2号选手的主要竞争对手的压力，确实也是合理的。问题的确没有那么简单。

whbns

KeyTo9_Fans 发表于 2016-8-17 08:42
$638512875$种分组方案不算太多，编个程序运行，很快就枚举完了。

使用long double数据类型计算概率，得 ...

夺冠概率最小的那12组方案用高精度算了下。除法保留300位，最终结果显示50位：

1 2 3 15 4 16 13 14 5 12 10 11 6 7 8 9
0.89910761028348250670415678686303171433246396281657

1 2 3 16 4 15 13 14 5 12 10 11 6 7 8 9
0.89910761028348250670414192708238402690800169136075

1 2 4 15 3 16 13 14 5 12 10 11 6 7 8 9
0.89910761028348250670563084927027833364090004624454

1 2 4 16 3 15 13 14 5 12 10 11 6 7 8 9
0.89910761028348250670562952631889866022396486097276

1 3 2 15 4 16 13 14 5 12 10 11 6 7 8 9
0.89910761028348250670415680304696869941702307406810

1 3 2 16 4 15 13 14 5 12 10 11 6 7 8 9
0.89910761028348250670414192724422339675901041655807

1 3 4 15 2 16 13 14 5 12 10 11 6 7 8 9
0.89910761028348250670577827169508579644252945531766

1 3 4 16 2 15 13 14 5 12 10 11 6 7 8 9
0.89910761028348250670577828640453663612950327743564

1 4 2 15 3 16 13 14 5 12 10 11 6 7 8 9
0.89910761028348250670563102729358516796884050879587

1 4 2 16 3 15 13 14 5 12 10 11 6 7 8 9
0.89910761028348250670562952809913172858345862838473

1 4 3 15 2 16 13 14 5 12 10 11 6 7 8 9
0.89910761028348250670577843353445564568591080661746

1 4 3 16 2 15 13 14 5 12 10 11 6 7 8 9
0.89910761028348250670577828802293033463798831965029

如果最小值确实在这12组中，那么夺冠概率最小的确实是第二组：
1 2 3 16 4 15 13 14 5 12 10 11 6 7 8 9

whbns

排序好的在这里
2      0.89910761028348250670414192708238402690800169136075
6      0.89910761028348250670414192724422339675901041655807
1      0.89910761028348250670415678686303171433246396281657
4      0.89910761028348250670562952631889866022396486097276
10    0.89910761028348250670562952809913172858345862838473
3      0.89910761028348250670563084927027833364090004624454
9      0.89910761028348250670563102729358516796884050879587
7      0.89910761028348250670577827169508579644252945531766
8      0.89910761028348250670577828640453663612950327743564
12    0.89910761028348250670577828802293033463798831965029
11    0.89910761028348250670577843353445564568591080661746

wayne

将这16个人的实力值换成 等差数列，或者其他的数列，会不会 结果完全不一样了

BeerRabbit

wayne 发表于 2016-8-17 13:32
将这16个人的实力值换成 等差数列，或者其他的数列，会不会 结果完全不一样了

如果仅仅是作为一个数学游戏，设定具有特定分值的实例还可以接受。比较合理的假设应该是给定一组在一定范围内的能力分值（从一定的分布中抽样产生），然后根据要求给出分组方案。而这里的所谓“要求”也不应该是“某最强者获得冠军的概率最大或者最小”，窃以为，既然是一个比赛，比较合理的设定思路是“使得比赛结果最难以预测”，即所有运动员的夺冠概率组成的分布的熵最大。