储物室有100个储物柜，100个人的号码牌被随机地锁在这些柜子中。这100个人可以在行动前一起商量一个对策。行动开始后，这100个人每人依次进入储物室并最多检查其中的50个储物柜，检查完后需要将储物室完全复原成进来之前的样子。一旦行动开始他们彼此之间就不可以再进行任何交流。他们必须每个人都拿到自己的号码牌才算获胜，假设这些人有没有策略能让他们有一个比较宏观的概率能够获胜？这一概率是多少？是否有使得获胜概率最大的最优策略？
乍一看可能会觉得，这若干个人彼此之间不能相互交流，那么就相当于彼此独立地选择，这个概率应该是\((\frac{1}{2})^{100}\)，一个很渺茫的概率。
给出如下策略：
给100个储物柜编号1-100，号码牌也同样编号1-100，号码牌编号为\(i\)的人进入储物室后，按照如下方案行动：
打开并检查编号为\(i\)的箱子。
如果打开的箱子中的号码牌编号为\(j(1\le j\le 100)\)，则下一步打开编号为\(j\)的箱子。
重复(2)直至找到自己的号码牌或者检查次数用尽。
为什么这个方法有效？先想一下储物柜-号码牌关系的数学结构。
置换：\(X=\{1,2,\cdots, 100\}\)，定义映射\(f: X\rightarrow X\)，如果第\(i\)个储物柜中放着\(j\)号码牌，则定义\(f(i)=j\)，则\(f\)是一个双射，从自身到自身的特殊双射也被称作一个。
循环：通过复合映射完成首尾衔接。例如如果\(f(1)=2, f(2)=5, f(5)=1\)，则\(1\rightarrow 2 \rightarrow 5 \rightarrow 1\)就构成了一个循环。
置换的循环分解：置换可以被分解为若干个循环。也就是说，对于置换\(f\)的值域中的任意元素\(x\)，一定存在\(n\)使得\(x=f^n(x)\)，这确保了在不限步数的情况下，上面的策略100%可以找到自己的号码牌。
那么如果限步数最多50步，那么上面的策略能够成功的条件就是：置换的循环分解中，不存在长度大于50的循环。
记存在长度为\(k\)的循环的事件为\(A_k\)，那么显然，\(\{A_k, k > 50\}\)为互斥事件，因为至多只能存在一个长度为50以上的循环。
\(k>50\)时，计算\(P(A_k)=\frac{C_{100}^k (k-1)! (100-k)!}{100!}=\frac{1}{k}\)，所以\(P(\bigcup_{k=51}^{100} A_k)=\sum_{k=51}^{100} \frac{1}{k}\)
\(P(W)=1-\sum_{k=51}^{100}\frac{1}{k} \approx 0.311828\)
还可以再想一下，如果有\(2n\)个人，每个人可以检查\(n\)个箱子，那么\(n\rightarrow \infty\)时，这个概率会接近多少？
\(\ln (2-\frac{1}{n+1})=\int_n^{2n}\frac{1}{x+1} dx\le \sum_{k=1}^n \frac{1}{n+k} \le \int_n^{2n}\frac{1}{x} dx =\ln 2\)
因此概率会接近\(1-\ln 2 \approx 0.306853\)。
