又100个囚犯

Frankenstein

太厉害了这么强大的想法都能想出来，但是成功概率是怎么算出来的？为什么是1-1/51-1/52-......-1/100 ?还有更好的方法吗？

056254628

接10楼， 这是我引用别人的叙述： 比如3号箱子里放的是6号囚徒的名字（本题是编号），6号箱子里放的是11号囚徒的名字，。。。。。。n号箱子放的是3号囚徒名字。这样上述的数字串构成一个环，3-6-11-......-n-3。 这样，所有的1-100个数字，被分成了若干个环。环中的元素个数从1到100。 假设所有的这些环的元素个数都不大于50，那么按照37楼的方法，必定100个囚徒都能成功找到自己的名字。 如果有一个环的元素个数大于50，那么这个环里的所有相应数字的囚徒都不能找到自己的名字。 ----------------------------------------------------------------------------------------- 所以该方法能成功的概率就等于 将100个数字随机分成若个组（每组的数字首尾相接构成一个环，若每组的数字相同，但构成的环不同就算不同的分法），所有组的元素个数都不大于50的概率。 －－－－－－－－－－－－－－－－－－－－－－－－－ n个数随机分成若干组，每个组的成员头尾相接成环，所有分法的总数记作f(n)。 那么f(n)=n！ ----------------------------------------------------------------------- 100个数随机分成若干组， 最大环成员数为m（m>=51)的总分法数=P(100,m)/m*f(100-m) P(n,m)表示排列，等于n!/(n-m)! 那么每组成员数都不大于50的总数Num =f(100)-P(100,51)/51*f(49)-P(100,52)/52*f(48)-......-P(100,100)/100*f(0) =100!-100!/51-100!/52-...... -100!/100 =100!(1-1/51-1/52-......-1/100) 所以该方法，100囚徒都成功的概率=Num /f(100)=100!(1-1/51-1/52-......-1/100) / 100! $=1-1/51-1/52-......-1/100$ $=0.3118$

jmouse

如果箱子可以有顺序，前一个人看了50个箱子之后就能知道后一个人挑这50个是成功还是失败，他可以保证放在前面的50个箱子能让后一个人成功。 当然，这肯定不是题目的本意。 类似10楼的方法，构造一种新的方式：先打开和自己编号想同的，如果不是，则按照里面的数字往后数几个再打开。 用这种方式和10楼的方式最终的成功概率是不是一样？