概率趣题之百囚抓号

maomaobiao 发表于 2016-12-12 09:53
如果使用pizza的思路：
两个囚犯逃脱的几率是1/2 （对比完全随机的1/4）
四个囚犯逃脱的几率是2/4 * 2/3 *  ...

可能我哪有误解啊。只有两个囚犯逃脱的几率是百分之百啊：一个囚犯打开一个箱子，他的号码在就在，不在就肯定在另外一个箱子啊。

luckystar 发表于 2016-12-11 22:58
可能我哪有误解啊。只有两个囚犯逃脱的几率是百分之百啊：一个囚犯打开一个箱子，他的号码在就在，不在就 ...

如果2个囚犯，就只允许打开一个箱子。那就不是100%了。

老陈 发表于 2016-12-12 13:09
如果2个囚犯，就只允许打开一个箱子。那就不是100%了。

所以说必须亲眼看见，准确发现在哪一个箱子也不行？不过反正这也不是本题的重点。

全部随机选择就是0.5^2的概率，这是所有选择的平均值
但有一些必死的选择，比如大家都选1~50，或漏一个号码
排除掉这些概率为0的选项能提高剩下选项的平均概率

接下来可能就是要找比平均概率低的选择方案，如果能排除掉也能提高平均值
这个目前还没方向

notch 发表于 2016-12-12 17:19
全部随机选择就是0.5^2的概率，这是所有选择的平均值
但有一些必死的选择，比如大家都选1~50，或漏一个号码 ...

问题就是，使用一个什么策略，可以尽量避免那些低于平均值的选择。

从这个角度说，Jim的思路可以尽量避免重复，但是不一定能确保选择的逃生成功率高于平均值。

luckystar 发表于 2016-12-12 15:34
所以说必须亲眼看见，准确发现在哪一个箱子也不行？不过反正这也不是本题的重点。 ...

我没说清楚，两个囚犯两个箱子，每人只能打开一个箱子。条件应该是“找到”自己对应的号码，才能逃生；而不是“知道在哪里”就可以逃生了。

在两个囚犯的情况下，商量好每人打开一个箱子，避免重复打开，肯定是最优策略。而且这个策略和Jim的思路，在两个囚犯的情况下是一致。

Jim的策略在四个囚犯的情况下还没有算。今晚上暴力解决，可以和Pizza策略比较一下。

Jim 的策略，每个囚犯第一次打开自己编号对应的箱子，如果箱子里的号码不是自己的编号，就打开这个编号对应的箱子。

使用这个策略，在四个囚犯的情况下，惊人地把逃脱成功概率提高到了10/24
比Pizza策略好多了。我接下来会仔细想Jim的这个策略，真的很牛。

Jim的策略恰好在于“死循环”。

举例四个囚犯的情况：
比如两个箱子，1 和 4，如果对应的纸条号码是4和1，那么他们俩就可以逃脱。这种循环的size=2

如果箱子 1 对应的纸条号码是 1，其实也是一种“死循环”，循环的size=1

拓展到更多囚犯情况，只要死循环的size小于等于开箱的次数，并且排列的情况被“死循环”给塞满了，就可以逃脱。

---------------------------------------------

继续看四个囚徒的情况：

四个纸条放进四个抽屉，总共有4！=24中组合。在这些组合当中

被size=1的“死循环”塞满的情况，有1种
  1<>1  2<>2  3<>3  4<>4
被两个size=2的“死循环”塞满的情况，有3种
   1<>2<>1   3<>4<>3
   1<>3<>1   2<>4<>2
   1<>4<>1   2<>3<>2
被一个size=2和两个size=1的“死循环”塞满的情况，有6种
   1<>2<>1    3<>3   4<>4
   3<>4<>3    1<>1   2<>2
   1<>3<>1     2<>2   4<>4
   2<>4<>2     1<>1    3<>3
   1<>4<>1    2<>2     3<>3
   2<>3<>2     1<>1    4<>4

总共10种组合可以逃脱，使用Jim策略，在四个囚徒的情况下逃生概率达到10/24

用Jim策略解决六个囚徒的情况。

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

其中被size=1的死循环塞满的情况有1种

被三个size=2的死循环塞满的情况有15种（待验证）

被两个size=2和两个size=1的死循环塞满的情况有

被一个size=2和四个size=1的死循环塞满的情况有

被两个size=3的死循环塞满的情况有

被一个size=3，三个size=1的死循环塞满的情况有

被一个size=3，一个size=2和一个size=1的死循环塞满的情况有

maomaobiao 发表于 2016-12-12 17:25
Jim 的策略，每个囚犯第一次打开自己编号对应的箱子，如果箱子里的号码不是自己的编号，就打开这个编号对应 ...

哈哈，错进错处，还是猫兄厉害，妙手回春，才能让我的策略发挥预热