概率趣题之百囚抓号

maomaobiao 发表于 2016-12-12 17:41
Jim的策略恰好在于“死循环”。

举例四个囚犯的情况：

10/24这个值与我在允许信息传递规则下策略的成功率只相差2%（43.66%）。
这说明什么呢？
1.这个模型下信息价值很低
2.有信息成功率可以进一步提高，某些线索被我忽略了

maomaobiao 发表于 2016-12-12 04:16
用Jim策略解决六个囚徒的情况。

六个纸条放进六个箱子，有6!=720种排列组合

合计有276种可以逃脱。
8个囚徒，8个箱子。14736种。

先考虑第一步的最优选法。
第一步, 100个囚犯各选不同的箱子。
方便起见按他们的号码选， 1号开1号箱, ..., 100号开100号箱。

其后类推。

我看了标准答案了，还是令我震惊的。确实是个好题目。
但我想问如果题目变一变，如果打开抽屉的时候只能知道中还是没中，看不到号码，那应该怎么算概率？？

我成功地使用圈论和追圈法，把每个囚犯都能在前50次打开抽屉找到自己号码的概率，由随机打开抽屉成功率小到西甘的概率，提高到30%以上。
圈论和追圈法是我为这道题找优化策略时发现的。在我和霍爷的讨论中，霍爷多次指出我论述的谬误之处，最后把谬误的改正，把正确的完善，由我整理贴在这里。圈论和追圈法由霍爷命名。

下面介绍追圈法：
1号囚徒第1次打开1号抽屉，如果发现是1，追圈结束。如果号码不是1，是K1，就打开K1号抽屉，如果发现K1号抽屉里号码是1，追圈结束，如果不是1，下一个就打开发现的这个号码的抽屉。如此找下去。这样就一定在第100次或100次以内找到1号。这个不难理解，因为这100个抽屉里肯定有1号，而且不会打开以前已经打开过的抽屉，因为一个号码不能在多个抽屉里出现。
2号囚徒第1次打开2号抽屉，用和1号囚徒同样策略打开其它抽屉。
M号囚徒第1次打开M号抽屉，用和1号囚徒同样策略打开其它抽屉。
以上就是追圈法。

K1号囚徒打开的抽屉号码是：
K1，K2，...，Kn。
我们把这一串数字成为圈。
Kn号抽屉里的号码是K1。
n是K1号囚徒找到自己号码时打开抽屉的次数。以下称为圈的长度。如果n是51到100，我们称为失败，如果n是1到50，我们称为成功。
显然号码在同一个圈里的囚徒找到自己号码的时打开的抽屉个数相同。

如果失败就是存在长度不小于51的圈。
我们求长度为51的圈出现的概率。有多种方法可以求出，我们介绍3种方法。
方法1:
圈长度为51，意味着K1号囚徒第51次打开抽屉是找到自己的号码。
如果已知圈长度为51，并且K1号囚徒在圈里，那么K1号囚徒出现在位置51的概率为1/51。而K1号囚徒出现在位置51是圈长度为51的充分必要条件，由此得出出现长度为51的圈的概率为1/51。


方法2:
我们随便取51个抽屉，如果随便打开这些抽屉，有51!种打开方式。
打开第1个抽屉，这个抽屉号码为K1，如果抽屉里的号码是其它50个抽屉号码之一，就有可能成为长度为51的圈，把这个号码称为K2。有50种可能。
打开K2号抽屉，这个抽屉里的号码称为K3。如果K3是其它49个号码之一，就有可能成为长度为51的圈。有49种可能。
一直到打开最后一个抽屉，里面的号码是K1，这51个抽屉就成为长度为51的圈。
能够成为长度为51的圈的打开方式有50!种。
由此得出出现长度为51的圈的概率为50!/51!=1/51。与方法1吻合。
那位问了，圈的起点也应该是51吧？答案不是，是1，是最后那个抽屉里的号码。


方法3:
100个抽屉放100个号码，有100!种排列方法。
100个号码取其中51个号码，有C(100,51)种取法。这51个号码成为圈有50!种排列方法，不是51!，因为圈是没头没尾的。其它49个号码有49!种排列方法。那么所有排列含有长度为51的圈的概率为：
C(100,51)*50!*49!/100!=1/51
结果与方法1和方法2相同。(此方法思路由霍爷提供)。


用类似的方法可以求出出现圈长度为52，53，...，100的概率分别是：1/52，1/53，...，1/100。


对于圈长度不小于51的圈，出现不同的圈长度是相互独立的事件，这些概率可以相加。

由此得到K1号由于圈长度而失败的概率为：
F=1/51+1/52+...+1/100

主意：K1和所在的圈里所有囚徒都失败了。并且他们完全相关，命运相同。而不在这个圈里囚徒都不会失败，因为其它所有圈的长度最大是49。

所以F就是所有囚徒没有全部成功的概率。
那么所有囚徒都按追圈法打开抽屉，所有囚徒都能找到自己号码的概率为：
1-F=31.18%


以上结论只在允许打开抽屉个数不小于总抽屉个数的1/2时才成立。比如允许每个囚徒打开40个抽屉，上述结论不成立，因为可能存在2个圈同时失败。




Q&A：
Q：每个囚徒前50次打开抽屉找到自己号码的概率显然是1/2，怎么突然变成31.18%了？
A：这个31.18%不是囚徒前50次打开抽屉找到自己号码的概率，是这个囚徒在长度不大于50的圈的概率。


Q：囚徒在圈里能改变他自己前50次打开抽屉找到自己号码的概率吗？
A：不能。


Q：那成功率为什么不是50%？
A：因为实际打开抽屉时，囚徒不一定打开50个抽屉，找到自己的号码以后再打开其它抽屉没有意义，实际打开抽屉数有可能是1到49中的某一个数，囚徒打开的抽屉数少了，成功率自然变小。再有，这个囚徒虽然成功了，其他囚徒有可能失败，所以总的成功率比50%小是正常的。

Q：1号过去就只剩50%了，最终结果有这么大吗？
A：没错，用追圈法，1号所在的圈的所有人都过去了，成功率并没有改变。这就是追圈法策略的优越之处。

Q：如果囚徒数不是100，而是一个很大的数，由于调和级数是发散的，F值超过1怎么办？
A：不会的。
S(N)=1+½+⅓+¼+...+1/N
当N趋于无穷大时，S(N)也趋于无穷大。
但S(N)-S(N/2)却不是发散的，是收敛的，极限值为ln(2)。
欧拉定理告诉我们：
S(N)-ln(N)当N趋于无穷大时，这个式子趋于一个常数，叫欧拉常数。
所以当N很大时，我们可以认为：
S(N)-ln(N)=S(N/2)-ln (N/2)
都是欧拉常数，由此得到：
S(N)-S(N/2)=ln (N)-ln (N/2)=ln (2)

老陈 发表于 2016-12-13 20:40
我成功地使用圈论和追圈法，把每个囚犯都能在前50次打开抽屉找到自己号码的概率，由随机打开抽屉成功率小到 ...

先顶，慢慢看

老陈 发表于 2016-12-13 20:40
我成功地使用圈论和追圈法，把每个囚犯都能在前50次打开抽屉找到自己号码的概率，由随机打开抽屉成功率小到 ...

陈老师，如果规则允许每个囚徒获得之前囚徒的成功信息，那么成功率能提高多少？

Jimihandrix 发表于 2016-12-13 07:28
陈老师，如果规则允许每个囚徒获得之前囚徒的成功信息，那么成功率能提高多少？
...

比如1号囚徒把自己是否成功的信息告诉2号囚徒，2号还是要使用追圈法去找自己的号码。因此，这个信息没有意义。

如果允许1号告诉2号的位置，2号找到自己的号码以后随机打开49个抽屉，并且把其他囚徒位置告诉其他囚徒，那样就乱了。是否成功只取决于1号了，1号使用追圈法也没有意义了，与随机打开50个抽屉结果是一样的。所以规则不允许。

陈爷确实浑身是数学细菌。五六天前，哥在给陈爷说这道题的时候，叙述完题目之后，哥说，如果3天内能自主想出策略并能准确计算其成功率，智商125。当天就能，智商140。1小时内就行，智商150+

因为哥看完标准答案后，判断自己绝逼无法在3天内想清楚，即使想出策略也无法计算其概率。

没想到陈爷果然在1小时以内就当场说出了正确策略，并采用了跟标准答案不同的解释方法。

哥不信还有这么拽的人，于是追问每一步推理的过程。

果然，在其推理过程中，发现了漏洞。
但是，用错误的推理，怎么能得出正确的结果呢？

这有两个可能：
1. 错误的地方至少有两处，这些错误的地方错进错出，反而导致了正确的结果。拿俗话说，就是瞎猫碰上死耗子了。
2. 已经用直觉掌握了正确的推理，只不过语言暂时没有把这种直觉描述出来。

开始的一两天，我一直以为是第1个可能。但是后来，在经过对推理过程的润色和加工，可以作为完整的推理，我才明白，几乎可以肯定是第2种可能。也就是说，陈爷在得知题目1小时内就自行想出了策略并计算出了完整概率。
有图为证时间戳：