魔方吧·中文魔方俱乐部

标题: 监狱长给犯人们出的难题 [打印本页]

作者: yang_bigarm 时间: 2009-8-7 18:07:41 标题: 监狱长给犯人们出的难题

有一所监狱，里面有100个犯人。有一天监狱长想了一个难题，说是有一间屋子，里面放了100个
带有编号的盒子，这100个随机排列的盒子里分别放了这100个犯人的名字。现在要求犯人们依次
来到这间屋子里，从这些盒子里找出自己的名字，但是要求每个犯人只准打开50个盒子。每个
犯人完事之后，告诉监狱长自己的名字在第几号箱子里，然后就从这个屋子的另外一个门出去，
同时监狱长把所有的盒子恢复原状，于是这个犯人没有机会留下信息给后面进来的伙伴。如果
某个人找到了自己的名字，那么就认为这个人成功了。

但是监狱长的难题是要求所有的100人都要成功，否则就把他们都枪毙了。
现在犯人们可以事先商量一个打开盒子的策略，使得他们能有30%的机会让所有人都成功地找到自己的名字
请问他们是怎么做的呢？

这些盒子的外观都相同，只有编号不同。对随机排列的100个盒子，任意打开50个，有1/2的可能性找到自己的
名字，这都是已知的事实。

作者: 今夜微凉 时间: 2009-8-7 19:39:35

怎么连沙发都没人要~假设第一个人选的是1-50号盒子，就有1/2的概率选中~如果第二个人选的有N个〔N大于0小于50〕和第一个人一样，则当第一个人选对时~再次思考中~

[ 本帖最后由今夜微凉于 2009-8-7 20:07 编辑 ]

作者: yang_bigarm 时间: 2009-8-7 20:28:44

第一个人选1-50号，概率是1/2，第二个人选51-100号，概率也是1/2，那么他们都选中
自己名字的概率是1/2 x 1/2 = 1/4，就是25%，两个人的情况已经低于30%了吔。

那么100个人的情况怎么办呢？大家想想啊！

作者: lulijie 时间: 2009-8-7 20:40:51

如果要50%的人成功，可以100%做到。
要100%成功，30%可能做到，关键是如何安排的问题。

作者: lulijie 时间: 2009-8-7 21:12:53

假设a选择打开的盒子号码与b选择打开的盒子号码有m个号码相同。（0<=m<=50)
那么，a、b都看到自己名字的概率1/2*(50-m)/100+m/100 * (50-m)/100+m/100 * (m-1)/100=1/4-m/10000
所以无论如何安排方案，a、b两个人都能成功的概率<=1/4，对于全部100个人，全部成功的概率必然不可能达到楼主所要求的30%。

作者: superacid 时间: 2009-8-7 21:18:23

这题值得考虑....

作者: lulijie 时间: 2009-8-7 21:22:58

楼主的题目应该是出错了，这是不可能达到的目标。
可以把题目改为：
如何安排方案，才能使得他们全部成功的概率最大。最大概率是多少？

作者: superacid 时间: 2009-8-7 21:30:05

这个差得不多，都是估计一个界。

作者: xiaoshudian 时间: 2009-8-7 21:31:28

原帖由 lulijie 于 2009-8-7 21:22 发表
楼主的题目应该是出错了，这是不可能达到的目标。
可以把题目改为：
如何安排方案，才能使得他们全部成功的概率最大。最大概率是多少？

我同意你的看法：我的想法是：要达到最大的目标就是，在看之前：大家全部商量好：都看1~50号（如果编号不是按顺序，大家就实现商量号，看前面50个就行），这样，就恰好有50个人猜对自己的，也就是1/2概率.

[ 本帖最后由 xiaoshudian 于 2009-8-7 21:33 编辑 ]

作者: superacid 时间: 2009-8-7 21:36:39 标题: 回复 9# 的帖子

题目要求所有人都猜对，所以你的方法的概率是0

作者: lulijie 时间: 2009-8-7 22:05:26

编程模拟一下，结果：
假设所有人打开箱子的号码方案都是随机，试验10000次，没有一次100个人都成功.
所以觉得100个人都成功的概率应该很低。
-------------------------------------------
假设有100箱子、m个人，每个人可打开50个箱子，这m个人都看到自己的名字的概率为P(m)。
那么楼主的题目就是求P(100)的最大值。
不烦考虑一下，简单的情况。
P(2)最大值=1/4 ，两个人没有相同号码的方案概率最大。
P(3)=？
-----------------------------------
大家可以先求一下P(3)的最大值。这个应该比P(100)简单多了，但也不是看一眼就能得出结果的。
P(100)的概率应该是个小概率事件。

作者: catq2000 时间: 2009-8-7 22:09:30

这个问题有点难，不理解……

作者: noski 时间: 2009-8-7 22:23:37 标题: 回复 11# 的帖子

对于两个人的情况，如果这两个人都随机去选，是独立事件，那么p(2)是1/4；如果这两个人约定好，选不同的号码，那么这时P(2)就等于1/2。
对于四个人的情况，随机选的概率p(4)是1/16，但如果这三个人约定好，1选1和2，2选2和3，3选3和4，4选4和1，那么这时P(4)就等于1/12?

作者: schuma 时间: 2009-8-7 22:38:07

还是得让囚犯能有什么方法来传递信息，比如允许他们重新排列盒子之类的，否则每个囚犯发生的事情都是独立的，这道题就没什么意思了

作者: lulijie 时间: 2009-8-7 22:44:28

13楼的P(2)的定义和我的不一样，我的定义是100个箱子中有两个箱子中写有这2个人的名字，每个人可以打开50个箱子。

作者: lulijie 时间: 2009-8-7 22:58:45

3楼的
第一个人选1-50号，概率是1/2，第二个人选51-100号，概率也是1/2，那么他们都选中
自己名字的概率是1/2 x 1/2 = 1/4，就是25%，两个人的情况已经低于30%了吔。
那么100个人的情况怎么办呢？大家想想啊！
----------------------------------------------
我想当然的认为上面没错，结果5#计算的结果也出错。
第一个人选1-50号，，第二个人选51-100号，那么他们都选中的概率应该等于
50*50/(100*99)=25/99，不等于1/4，略大于1/4。
------------------------------------------------------
所以5楼的计算结果：
假设a选择打开的盒子号码与b选择打开的盒子号码有m个号码相同。（0<=m<=50)
那么，a、b都看到自己名字的概率1/2*(50-m)/99+m/100 * (50-m)/99+m/100 * (m-1)/99=100/99（1/4-m/10000）
当m等于0时取最大值25/99<30/100。所以楼主的要求还是不可能达到的

作者: lulijie 时间: 2009-8-7 23:18:13

可以按照13楼的定义来计算：
那么随机方案，P(4)的概率并不等于1/16。应该比1/16大。
电脑模拟计算Noski定义的随机方案的P(4)：
模拟1000000次，成功90095次。概率9%左右。

作者: boy315 时间: 2009-8-7 23:29:32

提示: 作者被禁止或删除内容自动屏蔽

作者: noski 时间: 2009-8-7 23:36:55 标题: 回复 18# 的帖子

boy31几是不是一个系列呢。。
如果可以留信息的话，每个人只要给身后的人留1 bit 的信息就够了：
比如第一个人选前50个，如果他告诉身后的人是1，那么让身后的人也选前50个，否则就选后50个。这样概率就能达到50%，只要第一个人中了就行了。
当然这1bit 的信息可以用咳嗽一声或惨叫一声来代替

作者: lulijie 时间: 2009-8-7 23:56:12

重新计算17楼的随机方案P(4)：
电脑模拟1千万次，成功次数920887。概率不等于1/16，说明每个人选中的事件不是独立事件。

作者: noski 时间: 2009-8-8 00:03:05 标题: 回复 20# 的帖子

你算的是四个人没有任何约定，每个人都随机的去选的吗？每个人选中的概率是1/2没有异议，那么为什么模拟结果不是1/16呢？
我怀疑是不是计算机中的随机数发生器有规律可循的缘故？

作者: lulijie 时间: 2009-8-8 12:20:21

对于21楼的质疑，我仔细考虑一下，觉得没理由不是独立事件，得到的概率应该等于1/16。
问题出在哪里?又重新运行多次，得到的概率分别是7.5%、11.2%。波动还挺大的，按理说1千万次的模拟，概率波动不应这么大？真的应该像Noski所说的随机序列生成器出了问题。
每个人随机选号码箱的号码组合，我设计了一个子程序，每运行一下子程序，就随机生成一个号码组合。
这个子程序是，先初始化随机序列生成器(以免每次生成相同的随机数序列)，再运用随机函数，随机生成号码组合。
按理说这个子程序设计应该没问题，但后来证实恰恰是这个子程序出了问题。问题在初始化随机序列生成器。
因为每个人随机设定他选择的号码组合，都要调用一次那个子程序，而每调用一下子程序，就初始化一次随机序列生成器。
最后造成每个随机数序列都不是完整的，每每被中断。
--------------------------------------------------------------------------
最后删除子程序中的初始化随机序列生成器的语句，将初始化随机序列生成器语句直接放在主程序调用随机函数之前。
重新运行程序，
1百万次，成功62640次
1千万次，成功624466次。概率非常接近 1/16=0.625

作者: noski 时间: 2009-8-8 12:27:59 标题: 回复 22# 的帖子

赞！看来一个程序里只要将随机数生成器初始化一次就够了，这可真是一个隐蔽的BUG。。

作者: lulijie 时间: 2009-8-8 12:33:19

计算p(4)，但如果这三个人约定好，1选1和2，2选2和3，3选3和4，4选4和1，那么这时P(4)就等于1/12?
---------------------------------
电脑模拟：1百万次，成功83375次，非常接近1/12。
P(4)中最大的概率是不是1/12，还有其他方案更佳么？
推广到P(m),概率最大的方案到底如何呢？ P(m)采用noski定义

作者: lulijie 时间: 2009-8-8 14:13:34

p(4)，方案：1选1、2，2选1、2，3选3、4，4选3、4，
模拟1百万次，成功167006次，概率接近于1/6。
所以P(4)的最大值不小于1/6。

作者: 小魔豆 时间: 2009-8-8 14:26:14

每次都恢复原样，和独立操作有什么区别啊。他们商量个屁啊。

作者: noski 时间: 2009-8-8 14:42:44 标题: 回复 25# 的帖子

这个方法比我那个有效，那么来猜测一下：
m为偶数的时候，约定前一半人选前一半的数字，后一半人选后一半的数字，那么概率：
P(m) = (m/2)! * (m/2)! / m!
验证一下：P(2) = 1/2，P(4)=1/6，P(6) = 1/20 ……

作者: lulijie 时间: 2009-8-8 14:51:53

p(6)，方案：第1、2、3个人选1、2、3号码，第4、5、6个人选4、5、6号码，
模拟1百万次，成功50044次，概率接近于1/20。
比其他方案概率好像都大。
----------------------------------------------
所以我的感觉对于P(m)，最佳方案是：将m个箱子随便平分成两组，一半的人都选这一组号码，另一半人都选另一组号码。这样的方案全部成功的概率最大。最大概率等于1/ C(m,m/2) 。       C(m,2/m)是组合数。
这样P(2)=1/C(2,1)=1/2
   P(4)=1/C(4,2)=1/6
   P(6)=1/C(6,3)=1/20
对于楼主的m=100
最大概率=1/C(100,50)≈1/10^29
---------------------------------------------------
不知我的感觉对不对。

作者: lulijie 时间: 2009-8-8 14:53:08

哈哈，楼上的观点和我想法一样阿，不知能不能证明。

作者: 如来佛猪 时间: 2009-8-8 15:17:55

不知道能不能改变箱子的位置..改变了会被监狱长复原吗?

作者: lulijie 时间: 2009-8-8 15:20:37

从2个人的角度来看，当他们选择的号码组没有共同的号码时，2个人都成功的概率最大，我在前面已有计算公式。
对于100个人都成功，应该是他们两两之间共有的号码数目越少越好。
而方案：一半人都选同一组号码，另一半人选另外一组号码。
这样，前一半人与后一半人两两之间就没有相同号码，是不是这样的安排，使得概率会最大呢？

作者: noski 时间: 2009-8-8 15:32:39 标题: 回复 31# 的帖子

不知如何证明这个方案是不是最大概率，用Windows自带的计算器算了一下，这100个人的50-50的约定的概率是9.9e-30，比随机选的概率7.9e-31提高了12倍以上，但还是很小的小概率事件。

作者: yang_bigarm 时间: 2009-8-8 15:57:46

以上说法都没有命中题目的要害．

作者: lulijie 时间: 2009-8-8 16:00:32

不传递信息给后面的人，是不可能做到楼主要求的30%的概率。

作者: lulijie 时间: 2009-8-8 16:51:28

如果不允许前面的人透漏任何信息（比如调换箱子的位置，调换写有姓名的字条等等）给后面的人，那么
假设第一个人选择打开的盒子号码组与第二个人选择打开的盒子号码组有m个号码相同。（0<=m<=50)
那么，它们都看到自己名字的概率1/2*(50-m)/99+m/100 * (50-m)/99+m/100 * (m-1)/99=100/99（1/4-m/10000）
当m等于0时取最大值25/99<30/100。
既然无论如何安排，前两个人都成功的概率已经小于30%，那么对于100个人，楼主的要求更是不可能做到的。

作者: noski 时间: 2009-8-8 17:01:12

也许前面对半分的策略并不是最好的策略。。

作者: lulijie 时间: 2009-8-8 17:39:31

只有提高每个人成功的概率才行。 1/2的概率远远不够。
100个囚徒从1到100编号，每个囚徒记住每个人的编号，
每个囚徒进去后，先打开，与自己编号相同的箱子，若找到自己的姓名，就终止。否则，按照箱子中写的名字，换成这个名字囚徒的编号，（这个编号肯定不是该箱子的号码），再打开该编号的箱子，一直进行下去，直到找到自己的名字或不能再打开箱子为止。
这样每个人成功的概率是多少呢？

作者: lulijie 时间: 2009-8-8 18:06:12

每个人成功的概率一样都是1/2，但前两个人都成功的概率达到37%左右。

作者: lulijie 时间: 2009-8-8 18:40:41

按照37楼的方法：
比如3号箱子里放的是6号囚徒的名字，6号箱子里放的是11号囚徒的名字，。。。。。。n号囚徒放的是3号囚徒名字。这样上述的数字串构成一个环，3-6-11-......-n-3。
这样，所有的1-100个数字，被分成了若干个环。环中的元素个数从1到100。
假设所有的这些环的元素个数都不大于50，那么按照37楼的方法，必定100个囚徒都能成功找到自己的名字。
如果有一个环的元素个数大于50，那么这个环里的所有相应数字的囚徒都不能找到自己的名字。
-----------------------------------------------------------------------------------------
所以该方法能成功的概率就等于
将100个数字随机分成若个组（每组的数字排列顺序不同也算不同的情况），所有组的元素个数都不大于50的概率。
---------------------------------------------------------------------------

作者: noski 时间: 2009-8-8 18:41:51 标题: 回复 37# 的帖子

一开始我就在怀疑这道题的正确性，想怎么可能把概率从十的负30次方一下子提高到0.3以上，可是这道题却无情的颠覆了我的直觉。。。这么好的解法。。。

作者: lulijie 时间: 2009-8-8 18:51:35

每个人成功的概率都等于1/2，要提高100个人都成功的概率，只有想办法，使得它们成功的情况都碰到一起，失败的情况也尽量遇到一起，这样可以大大提高总概率。
------------------------------------------
比如2个囚徒2个箱子的情况。
每个囚徒成功概率1/2，大家都成功的概率可以提高到1/2。
比如第一个囚徒选1，那么第二个囚徒选2。
这样第一个囚徒若成功，那么第二个囚徒也必然成功，
第一个囚徒若失败，那么第二个囚徒也跟着失败。
这样只要第一个囚徒成功，两个囚徒也成功，所有概率等于1/2。
这样尽管每个囚徒的概率都等于1/2，但由于把它们成功的情况碰到一起，失败的情况碰到一起，使得每个人成功的时候尽量不浪费掉，所有大大提升了总概率。

作者: lulijie 时间: 2009-8-9 11:23:56

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

作者: maO 时间: 2009-8-9 11:29:06

很难,又是概率问题,溜哒过~~~~~

作者: boy315 时间: 2009-8-9 17:20:24

提示: 作者被禁止或删除内容自动屏蔽

作者: yang_bigarm 时间: 2009-8-10 21:07:25

good ！！

lulijie 又一次成功地解决了我的问题。

大家一开始都把这个问题想成是概率的问题了，其实这个问题主要不是考概率的，所用到的
主要的知识是有限集合置换的循环，正如我们对一个复原的魔方做同一个公式，若干步之后
就会回到复原的状态，抓住这一点整体的考虑问题，就得到了上面的答案。

这个题目跟魔方的理论还是有一些关系的呦。

作者: 123wyx 时间: 2009-8-10 22:13:27

解法精妙
佩服！

作者: 如来佛猪 时间: 2009-8-10 22:13:44

呵呵.....还是有点不理解..我在看看想想

作者: 348307806 时间: 2009-8-21 12:53:44

此题明显有问题，先看的人传递不了信息给后面的，也不能再选一次的，其实事件就是100个单独的事件了，跟事先商量没有关系，

[ 本帖最后由 348307806 于 2009-8-21 12:55 编辑 ]

作者: yang_bigarm 时间: 2009-8-23 23:52:14

原帖由 348307806 于 2009-8-21 12:53 发表
此题明显有问题，先看的人传递不了信息给后面的，也不能再选一次的，其实事件就是100个单独的事件了，跟事先商量没有关系，

此题没有问题，这个问题用到的主要知识不是概率，老盯着概率当然无法理解答案了。

作者: lulijie 时间: 2009-8-24 00:08:30

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

作者: 小梁 时间: 2009-8-24 01:08:29

学艺术类的~~~高考数学不算分~~所以数学一塌糊涂~~~~看不明白~~~

作者: lulijie 时间: 2009-8-24 01:35:49

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

作者: 骰迷 时间: 2009-8-25 10:17:19

哇！精采！重點就是捆綁式猜測。

作者: 想笑：） 时间: 2009-8-25 10:50:56 标题: 回复 52# 的帖子

明白了，聪明，佩服……

作者: shadowyang 时间: 2009-8-26 23:35:06

其实，打开50个盒子后，犯人可以按照他的想法排放这50个签，这样，后面的人就可以比较轻易地找到自己了，第一个人有1/2的机会成功，后面的人第二个人成功的机会>1/2，具体是多少我没算呢，在之后估计前面成功了，后面就100%了，所以能达到30%

作者: Cielo 时间: 2009-9-22 00:44:16

一直把这个页面存着，但今天才仔细看这题，解法太强了

[ 本帖最后由 Cielo 于 2009-9-22 00:45 编辑 ]

作者: yang_bigarm 时间: 2009-9-22 23:19:05

原帖由 shadowyang 于 2009-8-26 23:35 发表
其实，打开50个盒子后，犯人可以按照他的想法排放这50个签，这样，后面的人就可以比较轻易地找到自己了，第一个人有1/2的机会成功，后面的人第二个人成功的机会>1/2，具体是多少我没算呢，在之后估计前面成功了，后面 ...

你这分明是在篡改题目嘛。

作者: ggggwhw 时间: 2009-10-21 01:42:10

(*总人数*)
renshu = 100;
(*实验次数:*)
cishu = 10000;
chenggong = 0;
For[kk = 1, kk <= cishu, kk++,
qiutu = {};
hezi = {};
haoma = Table[i, {i, 1, renshu}];
For[ii = 1, ii <= renshu, ii++,
fanghaoma = RandomInteger[{1, Length[haoma]}];
AppendTo[hezi, haoma[[fanghaoma]]];
haoma = Delete[haoma, fanghaoma];
];
For[ii = 1, ii <= renshu, ii++,
For[jj = 1, jj <= renshu/2, jj++;,
If[Length[qiutu] < ii,
AppendTo[qiutu, {hezi[[ii]]}],
AppendTo[qiutu[[ii]], hezi[[Last[qiutu[[ii]]]]]];
];
If[Last[qiutu[[ii]]] == ii, Break[]];
];
If[jj > renshu/2, Break[]];
];
If[Length[qiutu] == renshu, chenggong += 1(*; Print[qiutu]*);];
];
Print["成功次数" <> ToString[chenggong]];
Print["实验总次数" <> ToString[cishu]];
Print["成功的概率" <> ToString[chenggong/cishu // N]];

复制代码

虽然不是很清楚所谓的数字环的理论,但是我觉得这种方法还是不错的.上面是我按照该思想做的Mathematica 程序.当然未必是最短的程序,但是实验次数不是很多时,还是可以出结果的.
成功次数3108
实验总次数10000
成功的概率0.3108
经历的时间是174秒,我还是可以接受这么长时间的.
程序中的(*; Print[qiutu]*)改成Print[qiutu]后可以输出成功时的抽取方法.但是如果实验次数很大时,输出会很长的.如果实验10次成功2~4次那么输出一下可以形象地看出抽取的过程.

[ 本帖最后由 ggggwhw 于 2009-10-21 09:27 编辑 ]

作者: 4ky 时间: 2009-10-22 13:03:29

如果这样，那就有更高概率的做法，每个人记住自己后面的一个人的编号，第一个人打开1-50号箱子，如果后面一个人在这50个箱子里，就把自己的名字换到第1号箱子里，然后如果自己身后的人名字也在这里，就把这个人的名字换到第2号箱子里，如果后面的人的名字不在前50号箱子里，把2号箱子里放上比1号箱子里的号码大的号码，告诉后面一个人，自己看的是前50个箱子，这样后面进来的人，打开第1,2号箱子，如果没有发现自己的名字，如果1>2，就直接在3-50号箱子里找，如果1<2，就在53-100里面找，然后把后面一个人的号码放入第2号箱子，或者用号码的大小通知下一个人应该在哪一半里找自己的名字。

作者: brainyuan 时间: 2009-10-23 14:12:42

解出来了！
每个犯人先打开自己编号的箱子，如果不是自己，则打开里面名字的犯人编号的箱子，以此类推。
成功概率大于30%，因为100个箱子中出现大于50个元素的循环的概率不超过30%！

作者: zhang1qaz 时间: 2009-10-23 14:30:52

很复杂嘛，概率么学好。。。飘过

作者: zslswemz 时间: 2009-10-30 08:58:55

原帖由 yang_bigarm 于 2009-8-7 18:07 发表
有一所监狱，里面有100个犯人。有一天监狱长想了一个难题，说是有一间屋子，里面放了100个
带有编号的盒子，这100个随机排列的盒子里分别放了这100个犯人的名字。现在要求犯人们依次
来到这间屋子里，从这些盒子里 ...

说清楚事前可以交流,抽盒子后不能交流,那100个人全部成功的概率为

1/2)**100.
100个人全部成功的概率不可能大于等于30%的.

作者: zslswemz 时间: 2009-10-30 09:11:08

"监狱长把所有的盒子恢复原状"是包含将盒子的排列顺序也恢复原样.
此题肯定是题目翻译错了!

[ 本帖最后由 zslswemz 于 2009-10-30 09:12 编辑 ]

作者: 钟跃民 时间: 2009-10-30 09:16:20

这是一个值得我们思考的问题，但我还是不懂啊！

作者: pubsea 时间: 2009-11-18 14:07:05

依题目描述来看没有可能的

作者: ursace 时间: 2009-11-18 15:01:17

别说30%，就是万分之三也达不到，前面出来的不能给后面的通报，除非在打开箱子的时候可以留暗号，否则每个人进去不都是独立事件？那么最终的概率不就是（0.5＋0.02）^100= 3.98413791 E10^-29？

作者: ursace 时间: 2009-11-18 15:05:22

而如果可以在箱子中留纸条等作弊方式的话，那就很简单了，第一人开1～50个，抄纸上放第50个里，第二人开50～99个，抄纸条随便放一个里，后面的人只要都选第二人放纸条的箱子就可以全对，第二个人也可以选对，那么成功率就取决第一人的成功率，为0.5+0.02＝52%，大于楼主给定的30%的要求

作者: law294189476 时间: 2009-11-18 15:07:43

让盲拧高手先进去，把50个人的名字背下来，再让魔板高手把信息折成纸飞机……
飞机飞到的几率是百分之三十……

作者: 东莞的8 时间: 2010-10-26 00:27:41

原帖由 brainyuan 于 2009-10-23 14:12 发表
解出来了！
每个犯人先打开自己编号的箱子，如果不是自己，则打开里面名字的犯人编号的箱子，以此类推。
成功概率大于30%，因为100个箱子中出现大于50个元素的循环的概率不超过30%！

这个方法没有考虑到独立循环的情况吧？而且你那个“因为”是怎样出来的我也不是很清楚。

作者: 文天波 时间: 2010-10-27 23:26:10 标题: 这个是标准答案哈，最后的概率计算方法我就不算了，很难的写的，你一看就明白

犯人们先起个编号，1-100,100个人对应100个盒子，现在里面的盒子是随机的，进去的人把盒子改变位子，第一个进去的人叫1号，第二个人叫100号，第3个叫2号，第4个叫99号，依次类推。。第一个有1/2的机会找到自己，找的时候就找前面50个的，找到了就顺便看看有没的第2个人的位子有就把它给它放好，，第二个进去的人就找后面50个。
假如第一个人在进去的时候看见后面那个人的编码放到后面，那么它的位子就是和和子的100号换，那么如果第三个人是100号盒子换的就失败了，如果不是那么他们就一直做把盒子和犯人对人的动作，我小算了下概率，大概30%左右。。。

作者: 文天波 时间: 2010-10-27 23:38:42 标题: 补充

概率大概是1- 1/2- 1/ 6=1/3 的机会，，，说白了就是进去把盒子的位子挑下就OK了

作者: maO 时间: 2010-10-27 23:58:08 标题: 回复 70# 的帖子

不是说了吗，盒子动了没用，狱长在每个人进来前会把盒子归位放好。。。。

作者: hzchensenlin 时间: 2010-10-28 00:42:00

去年论坛里加分是这么容易的一件事情

作者: fallenjoker 时间: 2010-11-8 01:31:31

概率不会因为策略改变，因为他们不知道之前的犯人所猜对的是那一个箱子。

作者: godtm 时间: 2010-11-30 07:40:51

原帖由 yang_bigarm 于 2009-8-10 21:07 发表
good ！！

lulijie 又一次成功地解决了我的问题。

大家一开始都把这个问题想成是概率的问题了，其实这个问题主要不是考概率的，所用到的
主要的知识是有限集合置换的循环，正如我们对一个复原的魔方做同一 ...

楼主的题目里可是有“犯人完事之后，告诉监狱长自己的名字在第几号箱子里，然后就从这个屋子的另外一个门出去，同时监狱长把所有的盒子恢复原状，于是这个犯人没有机会留下信息给后面进来的伙伴。”原状的意思不包括里面的名字吗？

作者: lsx 时间: 2010-12-2 10:31:38

问题有解？怎么就置顶了？答案在哪里啊？看了前五页没看到………

作者: fhw 时间: 2011-1-11 20:38:19

应该是这题的正解。首先，将囚犯编号Q(1) Q(2) ……Q(100)，再将盒子编号B(1) B(2)……B(100)囚犯们先商定，Q(1)的名字在B(1)里， Q(2)的名字在 B(2)里，依此类推Q(100)的名字在B(100)里。当进入房间时，每个犯人找他自己的那个盒子，然后打开盒子里面的名字的盒子（如第一个盒子里是Q(16)，则打开B(16)，依此类推），再打开属于他在第二个盒子中发现的名字的人的盒子，依次继续下去，直到找到他自己的盒子或者打开五十个盒子。这就是解决问题的方法，但它到底是怎么解决问题的呢？把属于某个囚犯的盒子和在盒子中的姓名对应起来的过程，实际上是从100个名字的所有排列中随机地取一个排列。每个犯人都在排列的某个置换的其中一个位置，从他自己的盒子开始，到他找到自己的名字结束（如果他没有打开50个盒子的话）。如果恰好排列长度没有超过50的置换，则问题就解决了，所有囚犯都可以回家睡觉。。。。实际上，一个从1到2n的随机排列不包含长度超过n的置换的概率至少是1减去2的自然对数——大约30.6853％。要明白这件事，令n＜k≤2n，并找出所有长度为k的置换的排列C。总共有C（上标k，下标2n）种可能（k和2n上下平行，打出来变成这样了。。）而k个元素的置换种类共有（k－1）！种，另外2n－k个元素有（2n－k）！种排列方法，这些数的乘积为（2n）！/k。由于给定的排列中最多只有一个k－置换，所以存在k－置换的概率恰好是1/k。因此，没有长的置换的概率为1－1/（n+1）－1/（n+2）－……1/（2n）=1－H2n+Hn，其中Hm为前m个正整数的倒数的和，随着m的增大它将越来越接近1n m。因此所要求的概率大约是1-1n2n+1nn=1-1n2，当n=50时，囚犯的生还机率为31.1827821％。我书上的标准答案，不知对不对，打字好累。。。。。。。。

[ 本帖最后由 fhw 于 2011-1-11 20:40 编辑 ]

作者: 八目阿修罗 时间: 2011-2-16 04:28:15

原帖由 law294189476 于 2009-11-18 15:07 发表
让盲拧高手先进去，把50个人的名字背下来，再让魔板高手把信息折成纸飞机……
飞机飞到的几率是百分之三十……

最有创意的解法

作者: 雪原芒果 时间: 2011-3-12 16:32:47

题目似乎很难~~~思考ing

作者: 雪原芒果 时间: 2011-3-12 16:35:59

原帖由 fhw 于 2011-1-11 20:38 发表应该是这题的正解。首先，将囚犯编号Q(1) Q(2) ……Q(100)，再将盒子编号B(1) B(2)……B(100)囚犯们先商定，Q(1)的名字在B(1)里， Q(2)的名字在 B(2)里，依此类推Q(100)的名字在B(100)里。当进入房间时，每个犯人找他 ...

厉害ia，怎么想到的！！！

作者: 玉逸风 时间: 2011-5-11 08:27:22

这个问题我慢慢地考虑考虑！！！

作者: youxiqingjie 时间: 2011-7-21 13:12:58

曾经在国外的论坛上看到过类似的问题,
我们可以这样简化这个问题
假设盒子内的不是犯人的名字而是1-100的编号
这样,编号为n的犯人进入房间后,先找第n个盒子,如果盒子内的编号也为n,那么他成功了
如果盒子内的编号不为n,假设为k,再查看第k个盒子,以此类推,每次失败后,都查看第m个(m为上次查看的盒内编号)的盒子
这样也就简化为证明,不存在闭环长度大于100/2的情况的概率大于30%
具体论证过程就不给出了,对任意数目的盒子结果都是一致的

像LZ这样的问题,如果用名字的话...100个犯人甚至是1000个犯人要怎么记住其他犯人的编号...这个才是犯人们面临的最大的问题

作者: 神出鬼魔 时间: 2011-8-22 21:27:02

如果按原题目，那不是二分之一的50次方么？
那还有什么可能啊....

作者: ssxx 时间: 2011-12-31 00:53:16

42楼和77楼强！

作者: 冰天百华葬 时间: 2012-1-18 17:57:20

这题目可以使用树形图来解答

作者: 冰天百华葬 时间: 2012-1-27 20:39:27

哈，这我知道（哥是做实验+猜想）。将犯人们编上号码，每十个人为一组，将箱子也分为十组（在题目中yang-bigarm大人提到过，箱子是有编号的）。第一组犯人打开第1~5组箱子，第二组开第2~6组箱子，第三组开3~7组箱子，第四组开4~8组箱子，第五组开5~9组盒子，第六组开6~10组箱子，第七组开第1,3,5,7,9组盒子，第八组犯人开第2,4,6,8,10组盒子，第九组开第1,2,3,4,5组盒子，最后一组开第 6,7,8,9,10组盒子

作者: easyfly94334 时间: 2012-8-2 05:18:22

题目并没有说不是最后一起回答自己的盒子编号,也并没有限制进入房间的犯人顺序啊,那么要我说其实每个人根本不用打开50个盒子,只用打开一个盒子就行了
只需要出来告诉自已看到名字的那个人编号,而下一次就让得知自己编号的人进入,他只需打开除去自己编号以外的盒子然后记下名字就行了,简言之就是不关注自己,而关注别人

作者: lbccyxs 时间: 2012-9-28 14:59:00

这个问题按77楼的思路，其实也可以这样理解：如果按编号进行处理。也就是说只要前50个箱子打开没有出问题。那剩余的人打开就不会出问题。因为在找到自己过程中，只要是在找到自己（编号）前打开过的名字（编号）都已经属于安全的。它必然在这个组中（相互找到）。换句话说也就是打开满了前50个不同的号码后。剩下的人也必然打开剩余的50号码。自然属于100%的安全了。也就是说在50%的几率。然而。如果第一个没有打开完就已经找到编号。第二人又继续找。因排除前面打开过的编号后。成功的机会反而更大。所以在最不巧的情况下。成功的几率也有50%，至少有开50个不同的箱子的机会，如果说几率最低，也就是第一个的成功率最低！只有50%

作者: lbccyxs 时间: 2012-9-28 15:15:07

这个问题它的几率是50%，也就是前50个（不同编号按77楼方法）如果通过。那剩下的也必然过关。

作者: 陈纪东 时间: 2018-1-12 14:21:28

77楼正解

作者: 陈纪东 时间: 2018-1-12 14:21:59

牛掰

作者: 陈纪东 时间: 2018-1-12 14:22:32

虽然我还没看懂

作者: 陈纪东 时间: 2018-1-12 14:23:04

高速思考ing

作者: 陈纪东 时间: 2018-1-12 14:23:43

欢迎光临魔方吧·中文魔方俱乐部 (http://www.mf8-china.com/)