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+”也是错误的，article说 30% 的时间你可以拯救 100% 的囚犯。