先从一个暖身问题开始吧._./ 有一座监狱，关了三个死刑犯，就叫他们A、B、C吧。 有一天典狱长穷极无聊，就把三位死刑犯找来玩游戏。 典狱长说： 现在我给你们一个活命的机会。 在我的房间里有三个箱子，三个箱子里各自有一张纸条， 写着你们的名字，名字没有重复。 等等你们轮流进来，每个人可以抽自己的名字两次， 抽完以後就把名字摆回箱子里，然後离开。 离开後不会跟另外两个死刑犯碰面， 所以每个人的结果可以看成是独立的。 假如你们三个人都可以在两次机会里抽到自己的名字， 那我就让你们无罪释放。 假如三个人里有任何一人抽不到自己的名字，那就马上全部处决。 典狱长的盘算是，假如三个人都是随机抽的话， 因为是独立事件，所以获释的机率应该是(2/3)^3 = 8/27 < 1/3， 应该还算满安全的吧。 但是从死刑犯们的角度来看， 他们虽然在抽签後就不能沟通了， 但是在进房间抽签前有个机会可以讨论一下策略。 有办法做得比8/27更好吗？ 这个暖身问题是有最佳解的。 在给解答前，防爆雷。 一个直观的想法是，在任何情形下， 三个人获释的机率不会超过2/3。 把任何一次抽盒子的事件都独立出来看， 抽到自己名字的机率都是1/3。 所以假如三个囚犯都是随机抽的话， 在两次内抽到自己的名字的机率都是2/3， 三个人都成功的机率就是(2/3)^3。 所以囚犯想要提升存活机率， 直观上的方法是要让他们之间抽到自己的名字的事件有高度的正相关。 所以最好的状况是， 有2/3的机率三个人都抽到自己的名字， 另1/3的机率是三个人都抽不到自己的名字， 这样存活机率会达到极限，是2/3。 那，有没有办法达到2/3的最大值呢？ 有的。 以下再防爆雷XD 三位囚犯A、B、C先分别把三个箱子对应到自己的名字，假设分别是a、b、c。 A先进去抽箱子，策略如下。 A先抽对应到自己的箱子，也就是a。 假如a里面就是自己的名字，当然就解决了。 假如不是的话，看箱子里写的是谁的名字。 假如是B第二次就抽b箱，假如是C就抽c箱。 B和C也用一样的策略，先抽自己的箱子， 没中的话就抽箱子里对应的囚犯的箱子。 这样的话， 三个人无法活命的组合就只有箱子和囚犯构成一个长度为3的循环圈（3-cycle）。 所以，出事的机率是1/3。 事实上，这可以推广到n个囚犯，每人可以抽k次的问题。 同样的策略都可以导出最佳解。 比如说，如果k >= n/2的话， 囚犯不能存活的机率就是箱子的重排中有一个长度至少为k+1的循环圈。 用排列组合来算，囚犯的失败率就是 1/(k+1) + 1/(k+2) + ... + 1/n。 这个结果是有证明的。 现在回到我自己的问题。 回到三个囚犯抽两次的状况。 假如现在把条件放宽， 只要三个囚犯有两个能抽到自己的名字就释放， 那要怎样才会让存活机率最大化呢？ 当然，2/3现在变成下限了。 用前面的猜中机率正相关的想法来看， 存活机率的上限应该是1。 所以最好可以做到什麽程度呢？ 以下很随便的提出一个5/6的解法。 一样把囚犯和箱子一一对应，称作A、B、C和a、b、c。 A的策略和前面一样，也是先抽自己的， 然後一路抽箱子里对应的囚犯的箱子。 B和C的策略则是把不是自己的两个箱子抽完。 这样的话，六种组合里，唯一会失败的方案只剩下 A->a，B->b，C->c这个。 有办法做得更好吗？ --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 141.158.210.50 (美国) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1610208132.A.08F.html 感谢，我想这样的构造法是可行的... 但是後来看到下面的推文QQ 对！！ 所以稍微组织一下这个问题， 假设有n个囚犯，每个人可以抽k箱，释放条件是最多只有r个人猜错， 然後P_{n,k,r}是可以释放的最高机率， 那P_{n,n-1,1}=1，因为可以所有个人都抽一样的箱子... 因为没有想到这件事，所以问题变成trivial... 所以真正有趣的情况应该是从r=1，k<=n-2开始... ※ 编辑: MisatoMitumi (73.52.24.240 美国), 01/11/2021 03:22:07