[其他] 一題死刑犯問題
先從一個暖身問題開始吧._./
有一座監獄，關了三個死刑犯，就叫他們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://www.ptt.cc/bbs/Math/M.1610208132.A.08F.html
推
01/10 14:31,
3年前
, 1F
01/10 14:31, 1F
→
01/10 14:32,
3年前
, 2F
01/10 14:32, 2F
→
01/10 14:32,
3年前
, 3F
01/10 14:32, 3F
感謝，我想這樣的構造法是可行的... 但是後來看到下面的推文QQ
推
01/11 03:04,
3年前
, 4F
01/11 03:04, 4F
對！！
所以稍微組織一下這個問題，
假設有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
推
01/11 04:09,
3年前
, 5F
01/11 04:09, 5F