问题
假设有一百名囚犯，编号 1-100，你是监狱的典狱长，决定给这一百个犯人一个机会，让他们玩一个游戏，如果能通过，他们能够重获自由。
游戏的规则是这样的，首先将 1-100 编号的纸条随机的放入盖子上有 1-100 编号的 100 个盒子里，将这 100 个盒子放入到一个单独的房间中。游戏开始，每次一个犯人单独进入房间，他有打开 50 次不同盒子的机会寻找自己对应号码的机会，找完之后无论他是否找到自己的编号，都从另一扇门离开，所有打开的盒子都会被关上，全程他无法与其他囚犯交流，也不能在盒子上做标记。这样依次类推，直到所有的犯人都找寻完毕。在第一个犯人进入房间之前，所有的犯人可以在一起商量对策。如果一百个犯人全部都找到了自己的号码，那么所有犯人都会被释放；反之，如果有任何一个人没有找到自己的号码，那么所有的犯人会被立刻处决。
问题是，犯人是否可以采取什么样的策略可以提高所有人的生还机会咧？
策略
如果犯人不采取任何策略，那么所有人能够生还的概率为 ，基本等于就地处决了，但天无绝人之路，有一个策略可以使的所有犯人生存概率提升到 31%。
这一策略利用了链表中的环的知识，具体的步骤是这样的，犯人首先打开有自己编号的盒子，如果里面纸条的号码为自己的号码，则可以直接离开，如果不是，那么就去打开里面纸条号码对应的盒子，如果还不是，那去打开该盒子中纸条编号对应的盒子，依次类推，直到找到自己的号码，或者打开了 50 个盒子。
我们仔细思考一下这个策略就会发现，他是链表中环的应用，首先纸条和盒子的编号都是 1-100，意味着他们一定会形成一个或多个的环；从自己编号的的盒子开始，意味着犯人进入了有自己号码的那个特定的环，只要这个环的长度没有超过 50，那犯人一定可以找到自己的号码，不仅如此，这环里的其他人也一定能在 50 次以内找到自己的号码。
这样问题就转换成了100个盒子和纸条随即分配形成的环不超过 50 的概率，而这个概率算出来大约在 31%。
参考
- Gal, Anna, and Peter Bro Miltersen. “The Cell Probe Complexity of Succinct Data Structures,” n.d. https://doi.org/doi:10.1016/j.tcs.2007.02.047.