以前提到过，理论计算机这门课会邀请一些正在这边访问的教授来讲课，由于是本科生，所以这些教授一般都是讲些有趣的东西，比如之前的overhang 堆积木 - 能伸出桌面多远？。今天这次课，来自 Aarhus 的Peter Bro Miltersen讲了一个很有趣的游戏问题。
现在有 100 个箱子，有一个学生，一张写着他的名字的名片被放在某个随机选择的箱子里面。现在这个学生可以检查不超过一半也就是 50 个箱子，希望能够把它的名字找出来。
很显然，这个学生没有什么好的方法，随机选择 50 个箱子打开，有一半的概率可以发现含有它的名字纸条的箱子。
OK ，现在还是 100 个箱子，但是有 100 个学生，写着这些学生的名字的 100 张纸条随机放入 100 个箱子里(每个箱子恰好一张纸条)。现在每个学生可以检查不超过一半也就是 50 个箱子，每个学生希望能找到含有自己名字的箱子。如果在游戏中，所有学生都是独立的（他们不能互相讨论以及看到其他人的开箱结果），问所有学生都实现目标的概率有多大？
如果把每个学生的结果认为是独立的，那么成功的概率只有$ 2^{-100}$ ，但其实我们可以做的比这要好得多。事实上，让每个学生都找到含有自己名字的箱子的概率可以高达 0.3。
假设学生的名字就是它的编号，从 1 到 100。第$ i$ 个箱子里的编号是$ \pi(i)$ 。第$ i$ 个学生这样做：先打开第$ i$ 个箱子，再打开第$ \pi(i)$ 个箱子，再打开第$ \pi(\pi(i))$ 个箱子，以此继续下去，直到发现写着自己名字（也就是$ i$ ）的纸条或者打开箱子数到达 50 个为止。
那么当且仅当在$ i$ 到$ \pi(i)$ 这个置换中含有长度超过 50 的圈时，有学生找不到含有自己名字的箱子。这个概率是$ \sum_{j=51}^{100}1/j \sim \ln 2$ （注意一个随机置换里含有一个长度为$ j$ 的圈的概率为$ 1/j$ ）。
所以上面策略的成功概率为 $ 1-\ln 2 \sim 0.3$ 。
类似于以前提到的帽子游戏一以及帽子游戏二，我们要最大化一个团体都成功的概率，但是每个单个个体成功的概率又是一定的，那么我们只需要设计策略时，让大家要么几乎同时成功，要么几乎同时失败。就像上面的策略里，如果有人失败，意味着排列中有一个长度很大（大于 n/2 ）的圈，这个圈上所有人同时也会失败，通过把失败的实例重合到一起，这样就提高了总体成功的概率。
上面这个问题不是孤立的，它可以应用在 static data structure problems 的下界证明上。对于后面这个问题，在最近是一个很热门的研究领域，但在这里写了也没人看，知道这个问题的也不需要看，所以我只提一下我们还可以做什么，下面是一个 open problem ，可以直接得出一个 data structure 问题的一个下界，是一个可以写学术论文的题目：
Open problem ：假设现在有$ 2n$ 个箱子，$ n$ 个学生，学生们的名字纸条被放入随机选中的$ n$ 个箱子里。现在每个学生可以检查不超过一半也就是$ n$ 个箱子，以找到含有自己名字的箱子。问这时候学生可以采取什么样的策略最大化所有学生都成功找到含有自己名字的箱子的概率。
期望结果：证明指数级小的下界或者找到常数概率的策略。
有兴趣的可以参考The cell probe complexity of succinct data structures.
Q. E. D.
