在一个盒子里找到你自己的号码

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

Jeremy.. 7

这个难题在http://www.math.princeton.edu/~wwong/blog/blog200608191813.shtml中解释,并且该人在解释问题方面做得更好.

"所有囚犯被杀"的说法是错误的."你可以平均节省30+"也是错误的,文章说30%的时间你可以节省100%的囚犯.

这个难题在http://www.math.princeton.edu/~wwong/blog/blog200608191813.shtml中解释,并且该人在解释问题方面做得更好.

"所有囚犯被杀"的说法是错误的."你可以平均节省30+"也是错误的,文章说30%的时间你可以节省100%的囚犯.