algorithm - 在盒子里找到自己的号码

Question

100 名（或偶数 2N :-)）囚犯在一个房间 A。他们的编号从 1 到 100。

一个接一个（从 1 号囚犯到 100 号囚犯，按顺序），他们将被带入一个房间 B，里面有 100 个箱子（编号从 1 到 100）等待他们。（封闭的）框内是从 1 到 100 的数字（框内的数字是随机排列的！）。

一旦进入房间 B，每个囚犯可以打开 50 个盒子（他选择打开哪个）。如果他在这 50 个盒子中的一个中找到分配给他的号码，则囚犯可以走进 C 房间，并且在下一个从 A 房间走进 B 房间之前，所有的盒子都会再次关闭。否则，所有囚犯（在房间 A、B 和 C) 被杀死。

在进入房间 B 之前，囚犯可以就策略（算法）达成一致。房间之间没有办法交流（B房间也不能留下任何信息！）。

有没有一种算法可以最大化所有囚犯幸存的概率？该算法实现的概率是多少？

笔记：

• 随机做事（你称之为“无策略”）确实为每个囚犯提供了 1/2 的概率，但是他们所有人幸存的概率是 1/2^100（这是相当低的）。一个人可以做得更好！

• 不允许囚犯重新排列箱子！

• 当囚犯第一次找不到他的号码时，所有囚犯都会被杀死。并且无法进行交流。

• 提示：一个人平均可以救30多个囚犯，比(50/100) * (50/99) * [...] * 1要多得多

Answer 1

这个谜题在http://www.math.princeton.edu/~wwong/blog/blog200608191813.shtml有解释，这个人在解释问题方面做得更好。

“所有囚犯都被杀死”的说法是错误的。“平均可以救30+”也是错误的，文章说30%的时候可以救100%的犯人。

Answer 2

我发现这类问题的低技术解决方案始终是最好的方法。

首先我们对情况做一些假设

• 囚犯不都是程序员或数学家
• 他们不想死
• 守卫装备精良

所以他们明天有 0.005% 的机会看到，有一个非常简单和低技术的解决方案来解决这个问题。暴动

这都是关于损失与潜在收益的关系，囚犯的可能性远远超过警卫，并且将彼此用作肉盾​​，因为无论如何他们都是死人，如果他们不这样做，他们可以增加他们超越权力的机会a守卫，一旦他们拥有他的武器，那里的机会就会增加，帮助他们控制更多的守卫以获得更多的火力，从而进一步提高生存率。一旦警卫意识到发生了什么事，他们可能会跑到山上并封锁监狱，这会让媒体抬头，然后这是一个人权问题。

Answer 3

实现一个排序算法，根据里面的数字对盒子进行排序。

第一个犯人对 50 个盒子进行分类，第二个犯人对另外 50 个盒子进行分类并与第一个犯人合并。（注意，第二个犯人可以猜出前 50 个方框内的值）

在第二个囚犯之后，所有的箱子都将按顺序排列！！！

其他人都可以轻松地打开包含他们号码的盒子。

Answer 4

我不知道这是否被允许，但我能找到的最佳近似值是：

编辑：好的，我认为这是成功的。当然，我将此视为计算问题，我认为任何囚犯都无法执行此操作，尽管如果您不这样做，这很简单。

找到前 50 个素数，假设我们将它们保存在一个称为素数的数组中。

• 第一个 prissioner 进入 B 房间并打开第一个盒子并找到数字 m。
• 等待素数[1]^m（即 3^m）
• 打开框 2 并读取数字 --> n
• 等待 (primes[2]^n - 1) * primes[1]^m，即 (5^n - 1) * 3^m，他等待的总时间为 3^n * 5^n

重复。在第一个囚犯之后，他的总时间是：3^m * 5^n * 7^p ... = X

在第二个囚犯进入房间之前，分解 X。您事先知道已使用的素数，因此分解是微不足道的。这样做你会得到 m、n、p 等，所以第二个囚犯知道前一个囚犯使用的每个盒子/数字组合。

第一个杀死所有人的概率是 1/2，第二个将有 50 / (100 - n) （第一个尝试的次数为 n）第三个将有 50 / (100 - n - m)（如果 n + m = 100 则所有位置都是已知的）等等。

显然，下一个prissioner必须跳过已知的框（如果包含他的号码的框是已知的，则最后一个选择除外）

我不知道确切的可能性是什么，因为这取决于他们必须做多少选择，但我会说它非常高。

编辑：重读，如果 prissioner 在获得他的号码时不必停下来，那么整个群体的概率就会大大提高，正好是 50%。

EDIT2：@OysterD 这样看。如果第一个犯人可以打开 50 个盒子，那么第二个犯人就知道它的号码是否在任何一个盒子里。如果是，那么他可以打开其他 49 个（并通过这样做学习 100 个盒子的盒子/数字组合）并最终打开他的一个。因此，如果第一个 prissioner 成功了，那么每个人都成功了。请记住，每个囚犯都为对方提供了一种方法，可以准确地知道他打开的每个盒子的盒子/数字组合。

Answer 5

也许我没有正确阅读，但问题似乎是结构错误或缺少信息。

如果他在这 50 个盒子中的一个中找到分配给他的号码，则囚犯可以走进 C 房间，并且在下一个从 A 房间走进 B 房间之前，所有的盒子都会再次关闭。否则，所有囚犯（在房间 A、B 和 C) 被杀死。

那里的最后一句话是否意味着所有囚犯都在囚犯第一次找不到他们的号码时被杀死？如果没有，找不到号码的囚犯怎么办？

如果无法进行通信，并且每当囚犯进入 B 房间时，它总是处于相同的状态，那么就没有策略的可能性。

囚犯可以在离开房间 A 之前说出他们要打开哪个号码框。但是，当下一个囚犯进入 B 房间时，如果后续囚犯不知道他们是否成功（假设一个人失败并不是所有人都失败），他们仍然有与前一个囚犯相同的选择号码的几率（总是 1:100） .

如果一个人的失败就是所有人的失败，那么通过知道之前的囚犯打开了哪个盒子，并且凭借他们还没有全部被杀死的事实，每个连续的囚犯都可以将挑选错误盒子的几率降低一个盒子。即第一个囚犯为 1:100，第二个囚犯为 1:99，最后一个囚犯为 1:1。

Answer 6

囚犯可以同意囚犯 1 打开盒子 1-50。

如果他们都还活着，他们同意下一个囚犯打开盒子 2-51。（2 是任意的，但很容易记住这条规则）鉴于 P1 幸存下来，他的幸存几率现在是 50/99。当你知道前一个人找到了他的时候，你想避免打开一个盒子。

我不知道这是否是最优的，但它比随机的要好得多。

幸存的概率看起来像

50/100 * 50/99 * 50/98 *。. .50/51 * 1

Answer 7

我认为由于无法进行交流，因此最好的策略是

尽可能平均地分配每个囚犯的概率

我是否走在正确的道路上？

每个囚犯的可用信息：

• 幸存囚犯的数量，所以如果你有一个高效的箱子拣选系统，利用任何囚犯进入房间 B 的顺序，那么一个策略绝对是可能的
• 较早的囚犯选择了哪些箱子。当然，在运行过程中不可能进行任何交流，也不可能记住任何 100 次选箱排列。但是您可以在运行开始之前使用此信息在系统中进行计算。

我的看法：

1. 绘制一个有 2 列的数字表，第一列包含盒子编号（从盒子 #1 到盒子 #100）。然后每个囚犯可以选择 50 个盒子，无论他们选择什么盒子，他们都应该在第二列的相应行上打 1 分。
2. 然而，所有囚犯都必须永远不要两次捡起任何盒子。并且没有一个框可以标记超过 50。一些囚犯可能比其他囚犯获得更少的选择，因为某些框可能首先被填满到 50 分。
3. 当囚犯被转移到 B 房间时，他/她会打开他在上面标记的任何盒子。

Answer 8

相同的概念。

另一个采取：

1. 写下包含 50 个 1 和 50 个 0 的前 100 个二进制数的列表。
2. 将它们从低到高排序。
3. 1号犯人得到第一个号码，2号犯人得到第二个，3号犯人得到第三个，依此类推……
4. 每个囚犯都记得他/她的二进制数。
5. 当任何囚犯被转移到B房间时，他/她将他/她记住的数字的二进制数字与每个盒子匹配，最高位与最左边的盒子匹配，下一个最高位与最左边的第二个盒子匹配。 .. 最低位与最右边的框匹配。
6. 他/她打开任何与 1 匹配的框，并留下与 0 匹配的封闭框。

这将最小化概率，因为早期囚犯将获得与后来囚犯不同的数字，而数字靠近的囚犯将获得数字靠近。这并不能保证生存能力，但如果早期的囚犯确实幸存下来，那么后来的囚犯也有更高的幸存概率。

虽然我还没有想出确切的数字和基本原理，但这是我目前能想到的一种快速解决方案。

Answer 9

如果在有人找不到他们的号码时所有囚犯都被杀死，那么你要么保存 100 要么保存 0。没有办法保存 30 人。

Answer 10

这个问题没有任何时间限制，所以我建议囚犯决定每个盒子花 1 小时，并按照给出的顺序打开它们。如果第二个囚犯在 2 小时后被允许进入房间，那么他知道第一个囚犯在盒子 2 中找到了他自己的号码。因此他知道按顺序跳过盒子 2 并打开盒子 1、3、4...51 首先囚犯失败的几率是 50/100 假设第一个囚犯幸存，那么第二个囚犯获胜的机会是 50/99 所以答案似乎是 ((50 ^51)*49!)/100！根据谷歌的说法，这是 2.89*10^-9 几乎为零 所以即使囚犯知道这些盒子，以前幸运的人在里面找到了他们的号码也没有希望