监狱长给犯人们出的难题

lulijie

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)
所以按照37楼方法，100囚徒都成功的概率=Num /f(100)=100!(1-1/51-1/52-......-1/100) / 100!
                                                                                      =1-1/51-1/52-......-1/100
                                                                                     =0.3118

lulijie

此题主要涉及到条件概率问题：
想办法使得看起来是互相独立的事件，变成相互干扰的事件。
只有这样才能提高它们同时发生的概率。

lulijie

如何使得看起来是互相独立的事件，变成相互干扰的事件。
我举个例子，希望对大家对本题为什么能大大提高全部成功的概率的理解有帮助。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
有一所监狱，里面有100个犯人。有一天监狱长想了一个难题，他往一个盒子里面随便扔进去一个硬币，然后密闭，固定，使得它的结果不会改变。现在要求犯人们依次来到监狱长的屋子里，告诉监狱长那个硬币是正面还是反面，然后就从这个屋子的另外一个门出去，于是这个犯人没有机会留下信息给后面进来的伙伴。监狱长的难题是要求所有的100人都要猜对，否则就把他们都枪毙了。
现在犯人们可以事先商量一个猜硬币的策略，使得他们能有最大的机会活命，请问他们是怎么做的呢？
－－－－－－－－－－－－－－－－－－－－－－－－－－
如果大家都是随机猜，那么每个犯人的猜对事件相互之间都是互相独立，它们互不干扰，所以它们都发生的概率是(1/2)^100。
如果他们的策略是都猜正面，那么每个犯人的猜对事件相互之间就不是互相独立了，它们要么同猜对、要么同猜错。
也就是说每个犯人的猜对事件原本是互相独立的，经过这个策略，变成了相互干扰，大大提高了它们都发生的概率，从原先的(1/2)^100的概率，提高到1/2 的概率。