【Puzzle】孪生骑士

  |  

摘要: 《概率50题》孪生骑士

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


这是概率面试题连载第 15 期,我们继续看 《Fifty challenging problems in probability with solutions》 中的一道题。

往期的内容整理在这篇文章里;或者看这个 github 仓库


问题描述

Twin Knights

(a)

Suppose King Arthur holds a jousting tournament where the jousts are in pairs
The 8 knights in the tournament are evenly matched, and they include the twin knights Balin and Balan
What is the chance that the twins meet in a match during the tournament?

(b)

Replace 8 by 2^n in the above problem
Now, what is the chance that they meet?

(a)

8 个骑士进行淘汰赛,对阵图与上图这样的网球对阵图类似。8 个骑士的水平一样,任意一组比赛双方的获胜概率均为 0.5。8 个骑士中有两个人是孪生兄弟。
问: 这两个孪生兄弟在比赛过程中相遇的概率。

(b)

将 8 个骑士的淘汰赛改为 2^n 个人的淘汰赛,问这两个孪生兄弟相遇的概率。


思路参考

(a)

8 个骑士的比赛共有 3 轮,我们一轮一轮地考虑。

记事件 X1 为孪生骑士在第一轮相遇,若想在第一轮相遇,则它们必须同时被分到 (1, 2), (2, 1), (3, 4), (4, 3), (6, 5), (5, 6), (8, 7), (7, 8) 这八种情况之一。概率为

记事件 X2 为孪生骑士在第二轮相遇,若想在第二轮相遇,则需要它们两个被分到以下十六种情况的一种,同时它们两个还要都赢了

1
2
(1, 3), (1, 4), (2, 3), (2, 4), (5, 7), (5, 8), (6, 7), (6, 8) 
(3, 1), (4, 1), (3, 2), (4, 2), (7, 5), (8, 5), (7, 6), (8, 6)

概率为

记事件 X3 为孪生骑士在第三轮相遇,若想在第三轮相遇,需要它们两个其中一个被分到 [1..4] 中的一个,另一个被分到 [5..8] 中的一个。且他们在前两轮的共四场比赛都要赢,概率为

把 X1, X2, X3 这三种情况的概率加起来,得到孪生骑士相遇的概率

(b)

记事件 Xi 为孪生骑士在第 i 轮相遇,其中 i 取值为 1, 2, …, n,共 T = 2^n 人。

对第 i 轮,将 1 ~ 2^n 连续地分为 B = (2^n)/(2^(i-1)) 个桶,每个桶 C = 2^(i-1) 个元素。孪生骑士需要在编号为 (2k+1, 2k+2) 的相邻桶中(k=0,1,…,(2^n)/(2^i) - 1),相邻桶的组数为 N = (2^n)/(2^i),孪生骑士在满足要求的桶中的概率为

孪生骑士在第 1,2,…,i-1 轮中,共有 (i-1) * 2 场比赛。这些比赛还要赢,概率为

将两个概率相乘就是孪生骑士在第 i 轮相遇的概率

孪生骑士相遇的概率为


蒙特卡洛模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import numpy as np
import operator
from multiprocessing import Pool
from functools import reduce

def P(n):
return 1 / (2 ** (n - 1))

def run(n):
l = np.random.permutation(ladder)
for _ in range(1, n + 1):
for i in range(0, len(l), 2):
if l[i] + l[i + 1] == 1:
return 1
if np.random.rand() < 0.5:
l[int(i / 2)] = l[i]
else:
l[int(i / 2)] = l[i + 1]
l = l[:int(len(l) / 2)]
return 0

def test(n):
T = int(1e5)
np.random.seed()
y = (run(n) for _ in range(T))
return reduce(operator.add, y) / T

def main(n):
print("n = {}: P(n) = {}".format(n, P(n)))
args = [n] * 8
pool = Pool(8)
ts = pool.map(test, args)
for t in ts:
print("P(twin knight meet): {:.6f}".format(t))
print()

for n in range(3, 7):
global ladder
ladder = range(2 ** n)
main(n)

模拟结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
n = 3: P(n) = 0.25           
P(twin knight meet): 0.249970
P(twin knight meet): 0.249815
P(twin knight meet): 0.250011
P(twin knight meet): 0.249984
P(twin knight meet): 0.249990
P(twin knight meet): 0.250079
P(twin knight meet): 0.249889
P(twin knight meet): 0.250108

n = 4: P(n) = 0.125
P(twin knight meet): 0.124822
P(twin knight meet): 0.124963
P(twin knight meet): 0.124807
P(twin knight meet): 0.125172
P(twin knight meet): 0.124867
P(twin knight meet): 0.124937
P(twin knight meet): 0.124887
P(twin knight meet): 0.124992

n = 5: P(n) = 0.0625
P(twin knight meet): 0.062401
P(twin knight meet): 0.062294
P(twin knight meet): 0.062492
P(twin knight meet): 0.062508
P(twin knight meet): 0.062588
P(twin knight meet): 0.062417
P(twin knight meet): 0.062393
P(twin knight meet): 0.062459

n = 6: P(n) = 0.03125
P(twin knight meet): 0.031231
P(twin knight meet): 0.031373
P(twin knight meet): 0.031206
P(twin knight meet): 0.031259
P(twin knight meet): 0.031189
P(twin knight meet): 0.031246
P(twin knight meet): 0.031311
P(twin knight meet): 0.031256

Share