囚徒的策略

wangix

A hundred prisoners, each uniquely identified by a number between 1 and 100, have
been sentenced to death. The director of the prison gives them a last chance. He has a cabinet
with 100 drawers (numbered 1 to 100). In each, he’ll place at random a card with a prisoner’s
number (all numbers different). Prisoners will be allowed to enter the room one after the other
and open, then close again, 50 drawers of their own choosing, but will not in any way be allowed
to communicate with one another afterwards. The goal of each prisoner is to locate the drawer
that contains his own number. If all prisoners succeed, then they will all be spared; if at least
one fails, they will all be executed.
      There are two mathematicians among the prisoners. The first one, a pessimist, declares
                                                                        .
that their overall chances of success are only of the order of 1/2^100 = 8 · 10−31 . The second
one, a combinatorialist, claims he has a strategy for the prisoners, which has a greater than 30%
chance of success. Who is right?
我学组合学的时候，看到的一个例子
题目有不清楚的地方，我可以慢慢解释

wangix

100个囚徒，每人1个号（从1到100），监狱长给了他们最后一次机会，在100个抽屉里（抽屉也是编号的，一字排开）随机放了写有1到100的卡片。
每个囚徒，有50次机会开抽屉，如果50次以内找到自己的编号，则算成功。
所有人都成功的话，大家回家；有一个人失败，统统玩完。
请为囚徒们设计一种策略，该策略至少有30％的成功机会。（谢绝一切偷看，做标记的手法）

awei

这是一个关于素数的问题吧[br][br]-=-=-=-=- 以下内容由 awei 在 时添加 -=-=-=-=-
以素数101为模的例题，呵呵！

awei

[这个贴子最后由awei在 2010/06/17 08:42pm 第 6 次编辑]

   100+1=101等于素数，事先和所有的囚犯约定好，每个囚犯都编上号，囚犯进入房间后从左边第一个抽屉开始，分别编号为1,2,3，4,5等等直至100，那么根据101是素数的情况，每个囚犯要开完小于自己的囚犯号的51倍的倍数的抽屉，直到找出监狱长给自己的编号。大于101的数以101为除数，求出余数X，然后再开X号抽屉。这样所有囚犯存活的几率比较大，呵呵!

awei

这是我研究了好久的素数的一个性质，呵呵！蛮有意思的，呵呵！

y279592158

蛮有趣的嘛。

awei

很有趣的题，也很抽象的题，呵呵!

ccmmjj

  awei,你能证明你这个做法成功的机会不小于30％吗？我认为随机放的卡片对有规律的处理应该无效。

wangix

关键是证明

awei

[这个贴子最后由awei在 2010/06/21 07:20pm 第 1 次编辑]

[color=#0000FF]   这里是10个囚犯和10个抽屉，每个囚犯开5次，有俩个方案，不知道这个概率该怎么求?
   方案一