概率趣题之百囚抓号

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的死循环塞满的情况有

Howard 发表于 2016-12-14 03:46
帮陈爷纠正一个术语使用不当：

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

互斥事件，对这道题里概率的提高起到了非常重要的作用。