本文发表于《大众科学》的前博客网络，反映了作者的观点，不一定反映《大众科学》的观点
上周三晚上，我参加了在纽约市即将开幕的数学博物馆共同赞助的“数学相遇”项目。 2008年，数学家和前对冲基金经理格伦·惠特尼得知长岛一家致力于数学的小型博物馆即将关闭时感到沮丧。 他决定自己创办一家数学博物馆。 仅仅几年时间，他就筹集了所需的资金，这家博物馆是北美唯一一家致力于数学的机构，将于 2012 年 12 月开业。
根据惠特尼的说法，每次“数学相遇”（星期三是“第n次”）都是由数学家主导的公共项目。 昨晚，达特茅斯数学家和两本数学谜题书的作者彼得·温克勒在巴鲁克学院发表了题为“直觉失灵：拉伸你思维的谜题”的演讲。 我想深入研究他提出的一个谜题。 我之前就见过它，但它总是让我感到惊讶。
这种情况，像许多数学谜题的假设一样，有点牵强：一所监狱里有 100 名囚犯，虐待狂典狱长决定今晚所有囚犯要么被释放，要么死亡。 为了戏弄他们，典狱长决定让他们自己决定命运。 在一个单独的房间里，他会写下每个囚犯的名字，并随机放入一个盒子里。 囚犯们将一个接一个地进入房间，每人打开 50 个盒子。 如果每个囚犯都打开了装有自己名字的盒子，所有囚犯都将活下来。 如果任何囚犯未能找到自己的名字，所有囚犯都将死亡。 囚犯们可以事先决定策略，但一旦第一个囚犯开始打开盒子，他们就不能商量。 囚犯应该采取什么策略才能最大限度地提高他们看到下一个黎明的机会？
关于支持科学新闻
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻事业 订阅。 通过购买订阅，您正在帮助确保关于塑造我们当今世界的发现和思想的具有影响力的故事的未来。
显然，每个囚犯的随机选择不会带来很高的成功率。 每个囚犯有 50% 的机会找到自己的名字，但两个囚犯成功的机会只有 1⁄2×1⁄2=1⁄4，即 25%。 三个囚犯成功的机会只有 1⁄2×1⁄2×1⁄2=1⁄8，即 12.5%。 当我们达到 100 个囚犯时，概率仅为 (½)100=7.9×10-31=0.000000000000000000000000000079%。 （是的，我数了所有的零。） 为了理解这是多么不可能，请考虑一下，如果自宇宙大爆炸以来每纳秒都发生这种情况，囚犯仍然只有不到十万分之一的机会幸存下来。 我们可以将几率提高到百万分之一吗？ 千分之一？ 信不信由你，我们可以做得更好：有一种策略可以在 30% 以上的时间里拯救囚犯。
当我第一次遇到这个谜题时，囚犯们在开始时都被分配了一个号码——他们在盒子里找到的是号码，而不是名字，我认为这让我更快地找到了解决方案的想法。 因此，从现在开始，我们假设囚犯们按照字母顺序排列自己，并根据该顺序分配号码，尽管任何编号都可以。 （这与最初的问题略有不同，因为它给了典狱长额外的知识，他可以选择一种策略来确保囚犯的厄运。 假设他随机将号码分配到盒子里可以解决这个难题。）
想出一个不是随机的开箱策略并不容易。 但正如我经常在辅导数学时告诉我的学生那样，如果你不知道该做什么，那就做一些事情。 做你能想到的唯一的事情——这胜过无所事事。 所以这就是我所做的。 囚犯决定打开哪个盒子的一种方法是从随机开始，然后使用盒子的内容来决定接下来打开哪个盒子。 例如，如果囚犯 1 打开盒子 5，而盒子 5 包含数字 7，则囚犯将接下来打开盒子 7，然后打开数字在盒子 7 中的盒子。
事实证明，这其中蕴含着正确策略的种子。 唯一缺少的是如何选择要打开的第一个盒子，事实证明，每个囚犯都应该从自己的号码开始。 完全披露：我没有自己想出答案，但我与我的数学研究生同学讨论这个问题时非常有趣，最终其中一位同学告诉我们如何解决这个问题。
为了了解这种策略是如何运作的，我将遵循温克勒的引导，并使用一个只有 10 个数字的“婴儿”示例，就像他在上周三的演示中所做的那样。 我们需要将数字分配到盒子的方式视为排列，这是一种对从 1 到 10 的数字集进行排序的方式。 假设与盒子对应的排列是：*
顶行上的数字代表盒子编号，底行上的数字是盒子中的数字。 我们也可以用所谓的循环表示法来写排列：（1 7 3 4）（2 5）（6 10 8 9）。 第一个循环（1 7 3 4）表示盒子 1 中的数字是 7，盒子 7 中的数字是 3，盒子 3 中的数字是 4，盒子 4 中的数字是 1。 第二个循环（2 5）表示盒子 2 包含数字 5，盒子 5 包含数字 2，第三个循环（6 10 8 9）表示盒子 6 包含数字 10，盒子 10 包含数字 8，盒子 8 包含数字 9，盒子 9 包含数字 6。 两行表示法和循环表示法是书写相同排列的等效方式。
如果 10 名囚犯每人可以选择 5 个盒子，并且每个囚犯都从自己的号码开始，我们看到囚犯 1 将按顺序打开盒子 1、7、3 和 4。 在盒子 4 中，他找到了自己的号码 1。 囚犯 2 只需打开盒子 2 和 5 即可找到自己的号码。 每个囚犯依次找到自己的号码，因此他们都获得了自由。 您可以通过从排列顶行的任何数字开始，并检查返回该数字需要多少步来自行检查这一点。
如果我为盒子选择了不同的排列会怎样？ 让我们试试这个：*
用循环表示法写成，这个排列是（1 3 5 6 2 9）（4 8 10）（7）。 囚犯 1 按顺序打开盒子 1、3、5、6 和 2。 在盒子 2 中，他找到的是数字 9 而不是 1。 太晚了——这是他的第五个选择。 他没盒子了。 在这个游戏中，他的第六个选择包含他的号码这一事实并没有任何怜悯。 事实上，号码在第一个循环中的人都没有找到自己的号码。 当他们打开第五个盒子时，他们都只差一步。 号码在其他循环中的囚犯确实找到了自己的号码：囚犯 7 立即在自己的盒子里找到了，囚犯 4、8 和 10 在第三次尝试时找到了。 唉，这个群体注定要失败，因为囚犯 1、2、3、5、6、2 和 9 都未能找到自己的号码。
我选择的第一个排列的关键是其中没有长度大于 5 的循环。 包含您的号码的循环的长度与您必须打开才能使用此策略找到您自己的号码的盒子数量完全相同。 如果有一个循环，比如有 6 个数字，那么任何号码在该循环中的人都会找不到自己的号码，囚犯肯定会输。 但是，如果排列的所有循环都小于 6 个元素长，那么每个人都会找到自己的号码。
同样的原理也适用于我们有 100 名囚犯的谜题，他们每人可以打开 50 个盒子。 如果将名字随机放入盒子中定义的排列具有长度超过 50 个数字的循环，则囚犯会死亡，因为每个号码在该循环中的人都将无法及时找到自己的号码。
为了计算成功的概率，我们需要弄清楚在 100 个元素的排列中，有多少比例的排列具有长度大于 50 的循环。 好处是，如果一个排列有一个长度为 51 或更长的循环，它就不能有另一个循环； 最多还剩下 49 个元素。 奇迹般地，事实证明，随机排列具有长度为 51 的循环的概率是 1⁄51，长度为 52 的循环的概率是 1⁄52，依此类推。 如果你想知道为什么，请继续阅读。 如果不想知道，请跳过下一段。
为了找到一个长度为 51 的循环，我们有 100 个第一个元素的选择，99 个第二个元素的选择，98 个第三个元素的选择，依此类推，直到第 51 个元素有 50 个选择。 因此，我们可以用 100×99×…×50 种不同的方式编写一个 51 循环。 但是其中一些循环是等效的。 为了使用一个小的、易于管理的例子，循环（1 2 3 4）等效于循环（2 3 4 1）。 它们只是以不同的顺序写下来，但都对应于排列
循环（3 4 1 2）和（4 1 2 3）也是等效的。 我们可以通过除以循环的长度来纠正此错误； 我们可以从任何数字开始写下相同的循环，这就是我们过度计数的程度。 在我们的例子中，这意味着除以 51。 因此，我们排列的 51 个元素已被分配。 我们还剩下 49 个元素，它们的任何排列都是可以接受的。 49 个元素的排列数是 49×48×47×…×2×1，也称为 49！（阶乘）。 将所有内容放在一起，我们得到
具有长度为 51 的循环的排列。 由于 100 个元素的总排列数为 100！（这是分数中的顶部数字），因此具有长度为 51 的循环的排列的分数正好是 1⁄51。 相同的推理适用于任何长度超过 50 的循环。
我们现在需要将所有杀死囚犯的排列加起来，这意味着所有具有长度超过 50 的循环的排列。 就概率而言，这是 1⁄51+1⁄52+…1⁄99+1⁄100≈0.688。 因此，剩余的比例 1-0.688，即 0.312，是找到没有致命循环的排列的概率。 这种策略带来了高达 31.2% 的成功率，比随机策略好无数倍（技术术语）。 好耶！ 只是不要考虑他们仍然可能全部死亡的事实。
这个解决方案因其稳健性而有趣。 如果您增加囚犯的数量（并将囚犯与猜测的比例保持在 2:1），您可能会认为您的成功机会会下降。 确实如此，但几乎没有。 对于任何这种情况，成功率约为 1-ln2。 （请记住，ln 是以 e 为底的对数；ln(x)=y 意味着 e^y=x。） 如果您将囚犯人数增加到 1,000，猜测次数增加到 500，或者将囚犯人数增加到 10 亿，猜测次数增加到 5 亿，则成功率就是这个值。 原因在于，对于较大的 n，失败的概率非常接近函数 1⁄x 从 n 到 2n 的积分。 由于对数的性质，这等于 ln2 ≈0.693，因此成功的机会约为 1-ln2≈0.307，即 30.7%。
我觉得获胜策略有点诗意。 囚犯们不可能接近胜利，只有一两个人未能找到自己的号码。 如果他们没有全部成功，那么每个号码在长链上的人都无法找到自己的号码。 那超过一半的人！ 该策略的性质意味着您从链条上离您的号码最远的点开始打开盒子。 但没有更好的策略； 从您自己的盒子开始是确保您甚至在正确的链条上查找的唯一方法。 它感觉像一种“团结就是力量”的态度。
彼得·温克勒的演讲描述了这个谜题和其他几个令人费解的谜题，尽管他没有时间像我在这里那样详细地介绍。 观众很喜欢尝试解决出现的谜题。 数学博物馆在 12 月开幕之前，正在共同赞助更多关于各种不同数学主题的数学相遇活动。 他们的下一位特邀演讲嘉宾是数学家和计算机科学家卡洛·塞金，他设计了受数学启发的艺术作品。
*更正（2012/7/19）：这些示例在原始帖子中放置不当。 它们现在处于正确的位置。