100 Prisoners Problem

问题描述

背景：假设有 100 名从 1 - 100 编号的囚犯，100张写有他们编号的纸条。这些纸条被放在密闭房间的 100 个盒子中，编号也是 1 - 100。
操作：每名囚犯可以依次单独进入房间，打开这 100 个盒子中的任意 50 个。
限制：完成后，他们必须还原并离开房间，并且无法以任何方式和其他囚犯交流。

在操作开始前，囚犯们可以商讨对策。
成功条件：所有囚犯在盒子中找到自己的编号。

策略

随机查看盒子

每个囚犯找到自己编号的概率为 \(\frac{1}{2}\)
成功概率 P(success) = \((\frac{1}{2})^{100} \approx 0.000 0000000000000000000000000008\)

循环链表策略

囚犯 \(P_a\) 进入房间后，先去找自己编号对应的盒子 \(B_a\)，如果 \(B_a\) 中的纸条是 a，则直接完成。
如果 \(B_a\) 中的纸条为 b (\(b \not= a\))，则 \(P_a\) 再去找盒子 \(B_b\) ...... 直到找到盒子 \(B_n(1 \leq n \leq 100)\)，其中的纸条为 a。

flowchart TB
    A(开始) --> Box_a
    subgraph Box_a
    b
    end
    subgraph Box_b
    x
    end
    subgraph Box_n
    a
    end
    b --> Box_b
    x -.若干步.-> Box_n
    a --> Box_a

根据策略定义函数 \(f: B \to B\)，含义：根据当前打开盒子中的纸条编号找到下一个盒子 \[ \begin{aligned} & f(B_x)=B_{(x+k)\mod 100}, \\ & 0 < x \leq 100, x \in \mathbb{Z}\\ & 0 \leq k < 100, k \in \mathbb{Z} \end{aligned} \]

定理 1 \[ \begin{aligned} & \forall i \in \{x | 0 < x \leq 100, x \in \mathbb{Z} \},\\ & \exists n \in \{x | 0 \leq x < 100, x \in \mathbb{Z} \},\\ & f^n(B_i) = B_i \end{aligned} \] 证明
即证 \(\exists n,\ (i + \sum_{j=1}^{n}k_j) \mod 100 = i\)
即证 \(\exists k',\ (i + k') \mod 100 = i,\, 0 \leq k' < 100\) 显然存在这样的 \(k'\)。

所以集合 B 由一系列不通长度的环形链表构成。这些链表构成集合 B 的一个划分。

引理 1. \(f\) 可逆
证明
\(\because\) 盒子中的纸条是唯一的
\(\therefore\) 任意两个不同的盒子，内部的纸条不相同
\(\quad\)即 \(\not\exists i,\ j,\ i \not= j, f(B_i) = f(B_j)\)
\(\therefore f\) 是单射。
\(\therefore f\) 可逆，且由于 \(f\) 的定义域和值域相同， \(f^{-1}\) 和 \(f\) 的定义域相同。

定理 2
根据引理 1 和引理 2，当 \(n \not= 1\) 时，\(f^{-1}(B_i) = f^{n - 1}B_i\)。
即囚犯可以通过执行 n - 1 次 \(f\) 操作找到对应的纸条。

所以只要保证不存在长度 > 50 的环形链表，囚犯就能按此策略找到自己的编号。
定义 \(Loop_n\) 表示长度为 \(n\) 的循环链表， \[ P(Loop_n) = \frac{环排列}{全排列} = \frac{\frac{P_n^n}{n}}{P_n^n} = \frac{1}{n} \] \(P(Loop_{n>50}) = \sum_{n=51}^{100}\frac{1}{n} \approx 0.6882\)
\(P(success) = 1 - P(Loop_{n>50}) \approx 0.3118\)

有 \(2n\) 名囚犯时

定义 \(H_n = \sum_{i=1}^n \frac{1}{n}\)
\(\begin{aligned} P(success) & = 1 - (H_{2n} - H_n)\\ & = 1 - (H_{2n} - \ln 2n) + (H_n - \ln2n)\\ & = 1 - (H_{2n} - \ln 2n) + (H_n - \ln n) - \ln 2 \end{aligned}\)

使用 Euler–Mascheroni 常数，
\(\lim \limits_{n \to \inf} (H_n - \ln n) = \gamma\)
\(\begin{aligned} \lim \limits_{n \to \inf} P(success) & = 1 - \gamma + \gamma - \ln 2\\ & = 1 - \ln 2\\ & = 0.3069 \end{aligned}\)

参考

1. The Riddle That Seems Impossible Even If You Know The Answer ↩︎
2. 100 Prisoners Problem ↩︎