Corn 的自留地

问题背景

和最经典的问题不太一样，改了一下

有100个囚徒，编号从1到100。

监狱长将100个编号随机放入100个盒子里，每个盒子一个编号。

所有囚徒每天都可以进入房间，打开最多50个盒子，寻找自己的编号。

当所有囚徒都找到了自己的编号后，就会释放出所有囚徒。

否则一个也不释放，下一天接着进行同样的游戏，不过盒子中的编号不同（和原版不太一样）

建模

整个问题的过程可以描述为一下的模式

首先有一个长度为n的数组，里面存放的是0到n-1的数字。

然后，同时也有n个囚徒，每个囚徒都有自己的编号0到n-1，它们可以对数据进行至多k次的随机查询，一旦查询到的数字等于自己的编号，则该囚徒就被释放。

然后，每一天，还未被释放的囚徒都会进行如上的查询过程，一直到所有囚徒都找到自己的编号为止。

代码实现

我们使用代码来模拟上述的过程

python# 包导入
import random

创建囚徒类

pythonSUCCESS = 1
FAILURE = 0

class Prisoner:
    def __init__(self, number):
        self.number = number

    # 随机找号
    def choose_randomly(self, boxes, k):
        n = len(boxes)
        targets = random.sample(range(n), k) # 随机决定要找的盒子
        # print(f"Prisoner {self.number} is looking for boxes {targets}")
        for i in targets:
            if boxes[i] == self.number: # 找到了，释放
                return SUCCESS
        return FAILURE
  
    # 按照经典解法找号
    def choose_wisely(self, boxes, k):
        n = len(boxes)
        target = self.number
        for i in range(n):
            if i >= k: # 已经找了k个盒子，停止
                break

            if boxes[target] == self.number: # 找到了，释放
                return SUCCESS
          
            target = boxes[target] # 下一个目标
        return FAILURE

模拟某一场游戏的代码

pythondef generate_boxes(n):
    # 生成长度为n的，各不重复的0~n-1的序列
    return random.sample(range(n), n)

def process(n, k, max_days=10, is_wise=False, info=False):
    # 生成盒子
    boxes = generate_boxes(n)
    # 生成囚徒
    prisoners = [Prisoner(i) for i in range(n)]

    # 开始游戏
    day = 0
    success_count = 0 # 成功找到自己编号的囚徒数量
    while success_count < len(prisoners):
        day += 1
        if day > max_days:
            if info: print("Out of days.")
            break

        # 刷新盒子
        boxes = generate_boxes(n)
        success_count = 0

        # 处理囚徒
        for prisoner in prisoners:
            result = FAILURE
            if is_wise:
                result = prisoner.choose_wisely(boxes, k)
            else:
                result = prisoner.choose_randomly(boxes, k)

            if result == SUCCESS:
                success_count += 1

        if info: print("Day", day, ":", len(prisoners) - success_count, "prisoners left.")


    if info: print("Game over.")
    return day

# 测试
process(100, 50, max_days=10, is_wise=False, info=True)

plaintext    Day 1 : 53 prisoners left.
    Day 2 : 44 prisoners left.
    Day 3 : 42 prisoners left.
    Day 4 : 49 prisoners left.
    Day 5 : 40 prisoners left.
    Day 6 : 49 prisoners left.
    Day 7 : 48 prisoners left.
    Day 8 : 58 prisoners left.
    Day 9 : 50 prisoners left.
    Day 10 : 43 prisoners left.
    Out of days.
    Game over.

模拟多场游戏的代码

pythondef simulate(times, n, k, max_days, is_wise):
    day_stats = [0] * (max_days + 2)
    for _ in range(times):
        day = process(n, k, max_days=max_days, is_wise=is_wise, info=False)
        day_stats[day] += 1

    return day_stats

# 测试
simulate(
    times=100, 
    n=100, 
    k=50, 
    max_days=10, 
    is_wise=True
)

[0, 29, 21, 17, 5, 9, 5, 4, 1, 3, 2, 4]

统计分析结果

pythondef analyse(day_stats):
    games_count = sum(day_stats)
    print(f"总共模拟了 {games_count} 次")
    print("-----------------------------------------")

    for i in range(1, len(day_stats)-1):
        day_count = day_stats[i]
        print(f"第 {i}\t天结束数量:\t{day_count}\t, 占比:\t{day_count/games_count*100:.2f}%")
  
    print("-----------------------------------------")

    count = 0
    for i in range(1, len(day_stats)-1):
        count += day_stats[i]
        print(f"前 {i}\t天内结束数量:\t{count}\t, 占比:\t{count/games_count*100:.2f}%")

pythontimes = 10000
n = 100
k = 50
max_days = 10

# print("无策略随机模式")
# day_stats = simulate(times=times, n=n, k=k, max_days=max_days, is_wise=False)
# analyse(day_stats)
# print()
print("有策略模式")
day_stats = simulate(times=times, n=n, k=k, max_days=max_days, is_wise=True)
analyse(day_stats)

plaintext有策略模式
总共模拟了 10000 次
第 1	天结束数量:	3149	, 占比:	31.49%
第 2	天结束数量:	2146	, 占比:	21.46%
第 3	天结束数量:	1470	, 占比:	14.70%
第 4	天结束数量:	1025	, 占比:	10.25%
第 5	天结束数量:	732 	, 占比:	7.32%
第 6	天结束数量:	414 	, 占比:	4.14%
第 7	天结束数量:	337 	, 占比:	3.37%
第 8	天结束数量:	235 	, 占比:	2.35%
第 9	天结束数量:	143 	, 占比:	1.43%
第 10	天结束数量:	104 	, 占比:	1.04%
-----------------------------------------
前 1	天内结束数量:	3149	, 占比:	31.49%
前 2	天内结束数量:	5295	, 占比:	52.95%
前 3	天内结束数量:	6765	, 占比:	67.65%
前 4	天内结束数量:	7790	, 占比:	77.90%
前 5	天内结束数量:	8522	, 占比:	85.22%
前 6	天内结束数量:	8936	, 占比:	89.36%
前 7	天内结束数量:	9273	, 占比:	92.73%
前 8	天内结束数量:	9508	, 占比:	95.08%
前 9	天内结束数量:	9651	, 占比:	96.51%
前 10	天内结束数量:	9755	, 占比:	97.55%

理论计算

设第d天之前所有囚徒成功找到自己的编号的概率为 $p_d$

由于每一天的游戏成功与否是独立的，设每一天所有囚徒都成功找到自己编号的概率为 $p$

那么 $p_d = 1-(1-p)^d$

接下来就只需要讨论两种策略下 $p$ 为多少

首先是使用随机抽取的策略

由于每个囚徒之间没有交流，所以每个囚徒能否找到自己编号的事件彼此之间是独立的

设 $q$ 为某个囚徒找到自己的编号的概率，那么 $p = q^n$

又因为 $q = \frac{k}{n}$

得 $p = (\frac{k}{n})^n$ ，进一步得到 $p_d = 1-(1-(\frac{k}{n})^n)^d$

当 $n = 100$ , $k = 50$ 时， $p_d = 1-(1-(\frac{1}{2})^{100})^d$

这个概率非常小，几乎不可能

然后是使用链式查找的策略

同样设 $q$ 为某个囚徒找到自己的编号的概率

实际上这个概率就等价于该囚徒得编号所在的"环"的长度 $\le k$ 的概率（因为只要它自己的编号所在的环长度小于查找机会数，就一定可以找到自己的编号，并且，由于自己的编号一定是环的最后一个元素，一旦编号所在环的长度大于查找机会数，就一定不能找到自己的编号）

再设 $q_i$ 为该囚徒的编号所在环的长度等于 $i$ 的概率

那么 $q = \sum_{i=1}^k q_i$

这里我不用排列组合的方式来算概率，感觉不太容易理解，直接用最直观的方式来算概率

首先我们要确定如何生成 $n$ 个囚犯所抽的编号盒子，也就是确定概率模型的随机事件

发现，我们可以从第一个盒子开始，一个个地放置囚徒们的编号，每个编号只能被放一次，直到所有盒子都被放置了编号

第一个盒子可以放 $n$ 个不同的编号，第二个盒子可以放 $n-1$ 个不同的编号，依次类推，最后一个盒子可以放 $1$ 个编号

所以， $n$ 个囚徒对应的编号盒子一共有 $n!$ 种不同的放置方式。

再来看 $q_i$ 这当前建立的概率模型的下有多少种不同的随机事件

这种条件下，我们已经事先直到要让某个确定囚徒的环的长度是 $i$ ，就可以按照如下的方式进行放置

当 $i = 1$ 时，直接在该囚徒的编号盒子中放置该囚徒自己对应的编号，只有一种方式
当 $i = 2$ 时，首先在该囚徒的编号盒子中放置除了他自己编号以外的编号，有 $n-1$ 种选择，再在选择的编号对应的盒子种放该囚徒对应的编号，1 种选择。共 $(n-1)·1$ 种选择
以此类推，当 $i = i$ 时，就有 $\frac{(n-1)!}{(n-i)!}$ 种选择

当把属于这条长度为 $i$ 的环对应的盒子放置完毕后，还剩下 $n-i$ 个盒子，这些盒子就随机放置剩下的编号，有 $(n-i)!$ 种选择。
那么，一共就有 $\frac{(n-1)!}{(n-i)!}·(n-i)! = (n-1)!$ 种选择

所以， $q_i$ 就等于 $\frac{(n-1)!}{n!} = \frac{1}{n}$ ， $q$ 就等于 $\frac{k}{n}$

发现怎么和随机的策略是一样的？？？每个囚徒找到自己编号的概率并没有增加，难道是计算出错了吗？

实际上，计算并没有出错，这种策略下每个囚徒找到自己编号的概率的确没有改变。而是囚徒找到自己编号成功与否这些随机变量之间变得不再独立了。

因为在这种策略下，倘若一个囚徒找到了自己的编号，那么可以肯定，和这个囚徒处于同一个环上的编号对应的囚徒都一定能找到自己的编号，反之亦然。

因此在这种策略下，仅仅知道了 $q$ 并不能计算出 $p$

所以我们要换一种方式计算 $p$ ，也就是直接计算 $p$ 的概率

$p$ 等价于 P(不存在长度 $> k$ 的环)，等价于 1-P(存在长度 $> k$ 的环)

当 $k \ge \frac{n}{2}$ 时，至多存在一个这样的环，这种情况比较简单，此处就只计算这种情况了

此时设 $q_i$ 为存在长度为 $i$ 的环的概率，那么 $p = 1 - \sum_{i=k+1}^n q_i$

此时 $q_i$ 的计算不再赘述，直接给出

$q_i = \frac{C_n^i·(i-1)!·A_{n-i}^{n-i}}{A_n^n} = \frac{1}{i}$

得到 $p = 1 - \sum_{i=k+1}^n \frac{1}{i}, k \ge \frac{n}{2}$

当 $n = 100, k = 50$ 时，使用下面的代码计算得到 $p$ ，再进一步算出各个天数对应的 $p_d$

pythonp = 1
for i in range(k+1, n+1):
    p -= 1/i
print(p)

# 进一步得到 p_d = 1 - (1-p)^d
for d in range(1, max_days+1):
    p_d = 1 - (1-p)**d
    print(f"Day {d}: {p_d:.4f}")

plaintext    0.3118278206898052
    Day 1: 0.3118
    Day 2: 0.5264
    Day 3: 0.6741
    Day 4: 0.7757
    Day 5: 0.8457
    Day 6: 0.8938
    Day 7: 0.9269
    Day 8: 0.9497
    Day 9: 0.9654
    Day 10: 0.9762

可以看到和模拟的结果是高度吻合的

100囚徒

问题背景

建模

代码实现

理论计算

首先是使用随机抽取的策略

然后是使用链式查找的策略

💬 评论区

写评论