囚徒的策略问题.doc

囚徒的策略问题 - 教育文库 囚徒的策略问题 一所监狱的典狱长是棋迷，所以监狱共设有361个牢房.监狱有361个犯人由于监狱里人满为患，典狱长决定处理掉这批犯人(其理由是这361颗棋子连一口气也没了，没气的棋子必须从棋盘上提掉)于是典狱长想出了下面的处理方法： 在一个只有一扇门的正方形房间的正中正放着一张方桌，上面又正放着一个围棋棋盘棋盘上放满361颗围棋子每颗围棋子的底面写有一个囚徒的名字每个囚徒轮流被引进房间后，允许翻开其中的360个棋子，以寻找自己的名字假如这个囚徒的名字恰好在那个没有被翻开的棋子下，那麽囚徒就输了只要有任何一个囚徒没有找到自己的名字，囚徒将被全体处死.反之假如每个囚徒都找到了自己的名字，全体囚徒被释放 当然，每个囚徒分开房间后不允许与其他囚徒交流下个囚徒进入房间之前，棋盘上所有的棋子都恢复原状 囚徒们的存活可能性有多大？这是典狱长的计算： 每个囚徒找到自己名字的可能性是360/361，因为每个囚徒找自己名字都是各自独立的事件, 那么361个囚徒都找到自己名字的可能性是(360/361)361=0.3673669即囚徒们的存活可能性小于37%，死亡率大于63%。

下面的问题是提出一个成活概率尽量大的翻棋策略(当然远远大于0.3673669) 最好的方法是: 将每个囚徒的名字与棋盘上的每个棋子建立一个任意的一一对应关系表, 这是容易办到的(譬如囚徒甲->天元, 囚徒乙->右上星位等等, 根据房间和棋盘的摆法，棋盘的方向是可以定义的). 然后让众囚徒记住这个表. 每个囚徒进入房间后第一个先翻开对应自己的那个棋子. 接着去翻开该棋子下面的囚徒名字所对应的棋子, 再根据下面的名字翻开对应的棋子. 等等, 依次类推, 一直到找到自己的名字或者只剩下一个棋子为止 为什么这个方法能进步找到名字的概率呢 ？〔温馨提示：众囚徒没有透视才能, 也无法在围棋子或棋盘上做记号，但他们的记忆力都很好……〕 显然, 在棋盘上的分布是361个囚徒的名字的一个排列, 而围棋九段将每个囚徒的名字与棋盘上的每个棋子建立一个任意的一一对应关系表那么是这些名字的另一个排列. 只要后一个排列不是前面排列的一个长度为361的循环, 那么可以看出按照此法众囚徒必定可以找到自己的名字因为此时可以分成假设干长度较短的循环，而长度较短的循环必定能在360步之前遍历循环的解释: 以1234为例, 4123是其一个长度为4的循环, 而2314那么是由长度为3和长度为1的两个循环组成)。

不难看出, 一个361名字的排列的所有长度为361的循环总数为360!个. 而361名字的所有排列总数是361! 这样只有360!/361! = 1/361的可能性, 我们建立的表正好是原来排列的一个长度为361的循环. 这时计谋失败 换句话说, 计谋成功的可能性是1-1/361 = 99.72%. 这也是一个囚徒找到自己名字的可能性. 361人找到自己名字的可能性竟然和一个囚徒找到自己名字的可能性一样! 实际上，安这种方法只要第一个囚徒找到了自己名字，就能保证所有的囚徒都找到自己名字 最后,典狱长有方法击败这个妙计吗？ 有, 那就是在每个囚徒出去后,不把棋子恢复原状, 而是打乱从新分布在棋盘上，或者把棋盘转个方向也行. 这样的话上面的讨论就不成立了, 361个囚徒都找到自己名字的可能性也回到了0.3673669 第 页 共 页。