星际迷航中的乌胡拉中尉如何克服天文困难

我们上个月的拼图任务是拯救由企业通讯官乌胡拉中尉（已故的尼谢尔尼科尔斯扮演）领导的八人星际迷航地面派对。船员们被外星种族 Catenati 囚禁在项链星云的一颗行星上。为了逃避，他们必须最大限度地提高执行任务的可能性，而该任务起初似乎只能提供令人沮丧的成功可能性。

八名机组人员被告知任务，同时被暂时关押在一个公共房间，在那里他们可以自由交流和制定战略。几个小时后，他们将一次一个地被带到一个叫做轮盘赌室的房间。这个房间有八个排成一排的按钮，每个按钮都经过编程以响应不同的机组人员。为了误导船员，每个按钮都随机贴上另一名船员的名字。每个机组成员最多可以按任意顺序按下四个按钮。每当他们按下按钮时，他们都会看到该按钮真正属于谁。在他们的四次尝试中，他们必须找到分配给他们的按钮。为了使船员自由，他们所有人都必须成功完成这项任务。如果其中一个失败，所有将被执行。在机组成员完成他们的尝试后，他们将被隔离，无法将信息传递给任何船员。

成功的机会似乎微乎其微。如果机组成员随机选择按钮，每个人将有 1 到 2 的机会找到他们的按钮。所有八人成功的几率仅为 256 分之 1，或约 0.4%。

但他们不必随意按下按钮。增加成功概率的一种方法可能是以某种方式平衡所有按钮按下。这给我们带来了第一个难题。

谜题 1

如果他们确保每个按钮被同样频繁地按下（而不是随机按下任何四个按钮），他们的生存概率可以提高多少？

Rob Corlett和JPayette很好地回答了这个问题，就像他们回答了所有其他问题一样。至于本专栏中谜题背后难以捉摸的中心思想，Rob Corlett、JPayette 和Jouni Seppänen对其进行了精美的描述，而Sacha Bugnon 则提供了一个计算机解决方案。

这是 Rob Corlett 的回答：

确保每个按钮被按下相同次数的一种方法是将囚犯分成大小相等的 4 人组。

每个组只按下与其组成员对应的按钮。因此，如果 A、B、C 和 D 都在同一个子组中，它们只按下 A、B、C 和 D 的按钮。

这将问题转变为询问每个囚犯被分配到正确组的概率，因为这样他们就可以保证在四次或更少的压力下按下他们的按钮。

用四个人填充第一组（以及第二组）的方式数是从 8 中选择 4 的方式数，即 C(8, 4) = 70。因此，将每个人分配到两组是 70。

只有一个分配将每个囚犯正确分配到正确的组，因此每个人都在正确的组中并且所有囚犯幸存的概率是 1/70，这比之前策略的 1/256 好 3.66 倍。 [但它仍然很小：只有 1.4% 的机会。]

谜题 2

有一种方法可以将原本惨淡的赔率提高 90 倍以上，达到 36.5% 左右，看起来很神奇！这种策略涉及使用循环或猜测链——因此提到了项链星云和链状星云（ catena是拉丁语中链的意思）。在该策略的基本形式中，每个机组成员首先按下带有他们姓名的按钮，然后继续按实际属于第一个按钮的机组成员姓名的按钮，依此类推，创建一个名称链。

让我们看看这在实践中是如何工作的。在图中，按钮显示为白色，其标签。下面的蓝色字母显示按钮的真正所有者。当第一位船员 A 进入轮盘赌室时，她首先按下按钮 A。这是C的按钮，所以她接下来按C，然后按E，最后按F，这实际上是A自己的按钮，所以她试了四次成功。请注意，按钮 ACEF 形成了一个由四个按钮组成的闭环。当船员C、E、F轮流时，他们也会绕着同一个闭环，从各自的地方出发，四次尝试也能找到自己的按钮。

这种排列还有两个较小的环，每个环有两个按钮：BD 和 GH。这四名机组人员将在两次尝试中找到自己的按钮。所以，通过这种安排，所有的船员都会成功，他们将获得自由。很明显，如果该安排仅包含长度为 4 或更少的循环，则所有机组人员都将成功并被释放。另一方面，如果有一个 5 个或更多的循环，则该循环上的所有工作人员将在四次尝试中找不到他们的按钮，并且工作人员将被处决。为了找到成功的概率，我们可以找到循环 5、6、7 或 8 的概率，将它们相加，然后从 1 中减去该总和。这比其他方法更容易计算，因为对于 8按钮，只能有一个具有 5、6、7 或 8 个成员的循环。

有8个！排列八个按钮的不同方式。但是当我们制作循环时，同一个循环占了其中的八个（ABCDEFGH 与 BCDEFGHA 形成相同的循环，与 CDEFGHAB 等相同）。因此，大小为 8 的循环的概率是 (8!/8)/8!，也就是 1/8。同样，大小为 7 的循环的概率是 1/7，大小为 6 的循环的概率是 1/6，大小为 5 的循环的概率是 1/5。因此，我们勇敢的船员成功的概率是 1 – (1/5 + 1/6 + 1/7 + 1/8)，即 36.5%，如前所述。

上述策略适用于任何数量的囚犯，并且随机方法的几率随着数量的增加而迅速增加。四个囚犯大约是七倍，六人是 24 倍，八人是 93 倍，100 名囚犯是惊人的（3.8 × 10 ²⁹ ）倍。理解这一巨大增长的关键在于，该方法将团队中每个成员的成功或失败与其他成员的成功或失败联系在一起。在很大程度上，它们都是一起成功或失败的。小组成功的概率并没有比一个人下降太多，随着囚犯人数的无限增加，从单个囚犯的50%下降到30.69%。另一方面，即使是少数囚犯，随机接近或什至“连按按钮”接近成功的概率也会迅速下降到非常接近于零。

如果这个策略背后的逻辑似乎仍然模糊，这里是Veritasium 的这个优秀视频中对 100 囚犯问题的分析。

谜题 3

这个谜题是关于 Uhura 中尉回忆童年游戏的故事，本质上是相同的谜题，但为六个人。作为提示，我建议为四个人解决这个问题。现在我们有了公式，我们可以很容易地计算概率。

对于四个人，最长循环仅为 2 或 1 的概率为：1 – (1/3 + 1/4) 或 41.7%，比随机选择增加七倍。

对于六个人，最长循环为 3、2 或 1 的概率为：1 – (1/4 + 1/5 + 1/6) 或 38.3%，比随机选择增加 24 倍以上。

谜题 4

随着我们的故事继续进行，事实证明，其中一名 Catenati 对Enterprise船员特别反感，并正在远程监控他们。他怀疑他们已经根据乌呼拉的图表想出了一些有效的策略。他决心在轮盘赌开始前溜进房间并故意改变按钮标签的顺序来挫败他们的计划。他能成功地挫败这个计划吗？登陆方有什么要特别小心隐瞒的？

在剧组战略讨论的很早的时候，乌呼拉的眼睛突然眯了起来。她向她的工作人员发出了一个信号，然后她转而用 Nicholese 说话，宣布：“请用 Nicholese 进行进一步的讨论。” Nicholese 是 Uhura 在她职业生涯早期为这种情况发明的一种新语言，以规避通用翻译器的使用。 “你一定注意到了可疑的 Catenati，”她继续说。 “他可能会试图破坏我们，所以我们需要修改我们的计划。这是我们需要做的……”

Uhura 概述了新计划，直到她对她的每个船员都非常了解它感到满意为止。然后她沉思着，眼中带着遥远的神色，“我以一位 20 世纪标志性女演员的名字命名 Nicholese。我很高兴我坚持让星际舰队将其作为我们所有船只的标准。”

她转身面对船员。 “就是这样，军官们。你知道该做什么！”

我们不知道 Uhura 对她的团队说了什么。但是 JPayette 和 Rob Corlett 有一个非常好的主意。这是罗布·科利特（Rob Corlett）：

如果邪恶的 Catenati 听说他们正在使用这种策略，那么他可以切换显示屏上显示的名称，以确保周期长于 4。

为了打破这一点，囚犯需要同意一个使序列随机化的秘密排序。他们这样做的方式是说“如果你看到 Uhura 的名字，然后转到标有 Chekov 的按钮。如果您看到显示 Chekov 的名字，请转到标有 Smith 等的按钮。”

这样一来，Catenati 的重新排序就无关紧要了，因为它只有在您知道工作人员对显示器上的名称做出反应的方式时才有效。不过，他们需要保守任何重新排序的秘密，否则它可能会再次被破坏。

正如我们所看到的，乌呼拉确保了这个秘密的安全。每个船员只需要使用相同的秘密命令，并确保邪恶的 Catenati 不知道它是什么。事实上，邪恶的卡泰纳蒂改变了顺序，实际上增加了船员成功的概率！

这就是发生的事情。乌呼拉是第一个被带到轮盘赌室的人。她按了三个按钮。没有一个是她的。她应该悲伤还是高兴？她屏住呼吸，按了她的第四个。她找到了她真正的纽扣！

她知道他们都会得救。

谜题 5

随着登陆方的规模无限增加，成功率的最大百分比是多少？你能解释一下为什么这种方法比随机按下按钮更有效吗？

JPayette 写道：

以上所有内容都直接概括为 2 n 个成员，每个成员最多允许按下n 个按钮。从谜题 2 中，我们推断他们成功的机会是

1 – （1/ k的n + 1 和 2 n之间的k总和）。

总和可以与区间 [ n , 2 n ] 上的 1/ x的积分进行比较，这使我们可以证明，随着n增长到无穷大，上述概率会减小以收敛到惊人的 1 – ln(2) ≈ 30.6%。 [实际上是 30.69% 到小数点后两位。]

Rob Corlett 补充道：

如果您不了解积分，您可以使用电子表格通过计算快速得出近似答案。一旦n达到大约 750，我就达到了 0.307，精确到小数点后 3 位。

我们已经在上面解释了为什么这种方法有效。所有大于 1 的循环由多个机组成员共享。所以他们的成功和失败是高度相关的。这是对“一切为了一，一为了一切”原则的例证。直接出自星际舰队手册！

感谢我们所有的贡献者。 JPayette 和 Rob Corlett 都提交了有价值的答案，这使得这个解决方案专栏看起来几乎是多余的。唉，我必须遵守我们的规则，即每个谜题栏选择一名获胜者。洞察奖授予 JPayette，以表彰这里和上一个难题中的贡献。恭喜！ Rob Corlett，您的贡献不会被遗忘。

下个月见，了解新见解！