Brain Teaser计算类 - 双败淘汰制

问题

在$2^n$个人（n>=1）参加的双败淘汰赛中，胜者组每一轮有一半的人胜出而继续留在胜者组。所以第n轮之后，胜者组第一次出现只剩1人的情况，此人的战绩是n胜0败。那么此时的败者组有多少人呢？

解答

首先，不难发现在第1轮到第n-1轮进入败者组的人数都为偶数，所以在第2轮到第n轮，败者组中没有发生轮空现象。因此，在第n轮后留在败者组的全体人员都进行了n场比赛，且他们的战绩均为n-1胜1败。

我们不妨改记胜者组、败者组为“0败组”，“1败组”。我们扩展定义“2败组”、……、“n败组”，并假设从“i败组”失败的人会进入“i+1败组”进入下一轮比赛。由归纳法不难得到，第n轮后“i败组”所剩的人数是$C(n,i)$. 因此第n轮后的败者组有$C(n,1)=n$人，已被淘汰的人数为${\sum }_{i=2}^{n}C(n,i)=2^n-1-n$人。

计算模拟代码如下：

def double_fail(n):
    wins, loses = 2 ** n, 0
    while wins % 2 == 0 and loses % 2 == 0:
        print(wins, loses)
        wins >>= 1
        loses >>= 1
        loses += wins
    print(wins, loses)
1
2
3
4
5
6
7
8

执行结果：

>>> double_fail(3)
8 0
4 4
2 4
1 3
>>> double_fail(4)
16 0
8 8
4 8
2 6
1 4
>>> double_fail(5)
32 0
16 16
8 16
4 12
2 8
1 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18