又100个囚犯

shshsh_0510

监狱人满为患，所以找了100个死囚，编号1到100 100个抽屉，每个放了一个号。 100个囚徒排着队，从第一个开始，每个人挑50个抽屉，如果这50个抽屉中有他的号，则成功，让下一个继续。 如果100个都成功，全部释放，如果有一人失败，全部枪毙。 在开始之前，100个人可以开会商量，但开始后就不能有任何信息传递了

gxqcn

我感觉很悬的，如果第一个人运气背的话就可能会失败， 反正是我现在还是无策。。。 有几个问题需要确认： 1、囚犯对自己的编号是否确知？以及是否知道其他囚犯的编号？ 2、在挑出的50个抽屉后，是否允许对它们作调整，比如排序等？

shshsh_0510

1。知道不知道有区别吗？ 都知道。 2。抽屉一旦放好就不调整了，但是前面挑的人不能告诉后面的人任何信息。 这个显然不能100%的保证，运气不好第一个人就挂了。但是存随机，活的概率太小了只有$0.5^100<10^(-30)$，几乎是死定了，如果有方法能增加一些几率也好。能增大到多少呢？

zgg___

“从第一个开始，每个人挑50个抽屉”，在这个过程中是挑一个就打开看呢？还是挑完50个抽屉然后一起打开看呢？也就是说犯人是否可以根据第一个抽屉里的号码来决定后面选择哪个抽屉呢？

shshsh_0510

挑一个就打开看。 印象中的zgg兄每次发言都思想深刻切中要害

gxqcn

来个比较无耻的方案： 前面抽抽屉的人将里面的号取走集中放于某指定抽屉中， 如果前两人幸运的话，则从第3个囚犯开始，只要选中这个抽屉就万事大吉了。 当然，以上前提需建立在： 1、抽屉里的“号”是可移动的，而不是刻画在其上的； 2、允许移动抽屉里的“号”。 不过，从 3# 的叙述可看出，上述无耻方案似乎不符合规则。{:2_34:}

shshsh_0510

6# gxqcn 狡猾狡猾的！ 所以我们将号“刻画在其上”

gogdizzy

假如1号抽前50个抽屉并且存活，那么就是说前50个里包含1号。 那么2号显然选取另50个存活概率大些。不过考虑到他们不能相互通信，那么就应该提前设计一个方案。 不然万一都瞎选，某个盒子从来没人选就坏菜了。 直觉觉得一个平均分配方案不错，就是每个抽屉都会被50个人选。

wool

To solve it, the prisoners must first agree on a random labeling of the boxes by their own names. (The point of making it random is that it makes it impossible for the warden to place names in boxes in such a way as to foil the protocol descibed next.) When admitted to the room, each prisoner inspects his own box (that is, the box with which his own name has been associated). He then looks into the box belonging to the name he just found, and then into the box belonging to the name he found in the second box, etc. until he either finds his own name, or has opened 50 boxes. it's not solved by myself

056254628

一种方法，见http://bbs.mf8.com.cn/viewthread ... tra=page%3D1&page=4 37楼的方法，成功概率计算见42楼，约为31.18% --------------------------------- 100个囚徒从1到100编号，每个囚徒记住每个人的编号， 每个囚徒进去后，先打开，与自己编号相同的箱子，若找到自己的姓名，就终止。否则，按照箱子中写的名字，换成这个名字囚徒的编号，（这个编号肯定不是该箱子的号码），再打开该编号的箱子，一直进行下去，直到找到自己的名字或不能再打开箱子为止。 成功概率= $1-1/51-1/52-......-1/100$