解一個有趣的數學（圖論、資訊理論）問題？

12-30

問題來自於水木，描述如下：
一個看守跟兩個囚徒玩一個遊戲。遊戲開始前兩個囚徒可以商量策略（兩位囚徒均熟悉遊戲流程），遊戲開始後，兩個囚徒再也不能相見。看守在一個8×8的棋盤擺了64個硬幣，硬幣有正面，有反面，是隨機的。看守叫來A，明確告訴囚徒A哪一枚硬幣下面藏著一張紙。而後，他要求A選擇翻轉棋盤中的一枚硬幣。注意：這個翻轉硬幣是必須的，而且只能是一枚(除了翻一枚硬幣以外，A不允許再有多餘的動作)。之後，他讓A離開。叫來B，如果B可以指出哪個硬幣下藏著這張紙，A和B都可以釋放，不然A和B都被絞死。
問：A和B商量哪種策略可以使得兩人存活的概率最高？

這題老題了，至少前年就看到了。而且不是存活概率高而是必然存活。且不止一種解。按照題目的關鍵字的英文谷歌一下就能找到不同的思路和解法

甚至reddit上也有討論

手機不方便翻牆，大家自己找下吧

更新：

這個頁面介紹的比較詳細，有圖而且容易懂，還配有交互界面：

Impossible Escape?

這個是reddit上的討論，裡邊的有些通俗的解釋也挺有意思的：

Chessboard of Coins

這個從信息理論分析的，適合比較熟悉編碼理論的閱讀（主要是漢明碼）：

Communicating Information through Randomness

有些方法本質是一樣的，只是解釋方法不同。

@楊帆的答案完全正確，給他補充一下解釋以及基於他的解法的一個操作性的解法, credit完全歸他所有。

解法：

把64個格子按照0~63的順序編好號。記第i個格子的硬幣狀態為 $a_i$ ，正面朝上記0，反面朝上記1.

對於每一個棋盤的局面 ${a_i}$ ，定義函數 $f({a_i}) = 0 ; ext{xor} ; k_1 ; ext{xor} ; k_2 ; ... ; ext{xor} ; k_m$ , 其中 $a_{k_i} = 1, ; i = 1...m$ . 即，把棋盤上所有向下的硬幣的坐標給異或運算，如果全朝上那就是0.

囚犯A:

看了任一棋盤局面 ${a_i}$ 後，計算出 $f({a_i})$ ，然後假設紙所在的位置坐標為 $j$ , 計算出 $l = j; ext{xor};f({a_i})$ 的值，然後翻轉坐標為 $l$ 的硬幣即可。

囚犯B:

直接計算新局面 ${a^{prime}_i}$ 對應的 $f({a^{prime}_i})$ , 即為紙條的坐標 $j$ 。

原因：

由於新局面 ${a^{prime}_i}$ 是局面 ${a_i}$ 翻轉坐標為 $l$ 的硬幣得到的，所以顯然有： $f({a^{prime}_i}) = f({a_i}) ; ext{xor} ;l$ . 又有： $l = j; ext{xor};f({a_i})$ ，從而有

$f({a^{prime}_i}) = f({a_i}) ; ext{xor} ;l = f({a_i}) ; ext{xor} ; j; ext{xor};f({a_i}) = j$

由此，B能夠以100%正確率指出紙條的位置。

Again, credit完全是 @楊帆的，這個解法想法非常不錯，觀點高，而且利用xor也不容易想到，非常牛逼。

來答一個。

下午看到了任宏達在群里貼的題和他的大概率存活解，感覺有優化的餘地，並且堅信這不應該是概率問題，應該是能100%存活的，於是在此基礎上推了一把，趁大家都去打牌/吃飯的時候得到了一種解法。

首先，問題抽象：每個狀態是一個頂點，總共2^n個，兩個狀態如果漢明距離為1則連一條邊。那麼每個點有n條邊。現在要給每個點染色，如果每個點的n個鄰點都正好是每種顏色一個，那麼問題解決。n在這裡是64。於是問題就變成如何構造這樣的染色法了。

手動染了n=1,2,4的情況，擴展到8的時候發現了規律：顏色為c(取值0~n-1)的點，如果改變第i(取值也是0~n-1)位的0/1值，那麼新的顏色為c XOR i即可。也就是說可以這麼構造：對任意一個頂點，它的顏色是它值為1的所有位數的XOR，這樣的圖滿足條件。適用於n為2的整數次冪的情況。

沒仔細驗證，看上去比較美觀，所以我覺得是對的。

補充：後來和同事腦補討論了一下n為任意值的情況，可以放棄一些顏色染或者多染一些顏色導致有的值鄰不到，兩者取優的話極限最小概率是1/sqrt(2)。不過任宏達有一個任何n都能75%的解，所以綜合起來應該是對於任意n成功率在75%~100%之間，圖像懶得畫了。

樓上匿名用戶說的對，這是一條老題，已經作為 puzzle 在網上出現過很多次了，

比如：

Using your Head is Permitted

答案是必然存活，一種策略可見：

Using your Head is Permitted

Mathematica程序

模擬了一下出了結果，貌似是對的，然後腦子抽抽了，現在還沒緩過來，Debug到現在，總算能用了

根據匿名用戶的思路寫的，就是把0替換成-1了，至於為啥，個人愛好。

qishi = Table[RandomInteger[], 64] /. {0 -&> -1};

zuobiao = Flatten@Position[qishi, 1] - 1;

fz = Fold[BitXor, 0, zuobiao];

j = 60;

l = BitXor[j, fz];

If[qishi[[l + 1]] == 1, xin = ReplacePart[qishi, l + 1 -&> -1],

xin = ReplacePart[qishi, l + 1 -&> 1]];

zuobiao2 = Flatten@Position[xin, 1] - 1;

Fold[BitXor, 0, zuobiao2]

說一個對於任意n個格子的棋盤75%成功的解法。

對每個棋盤的格子從0開始編號，對所有正面朝上的硬幣的編號進行求和，對n取餘數，得到k。假設白紙在m下面，那麼想辦法把餘數變成m。有兩種情況可以這樣做：

1. 若k-m對應的硬幣正面朝上，那麼把它翻過來。

2. 若n-k+m對應的硬幣的硬幣朝下，那麼把它翻過來。

上面兩個條件只要一個成立就能夠成功，所以成功率是3/4.

對於n為偶數的情況，如果k-m和n-k+m 相等的話，那是一定可以的，所以會比3/4略大。

對棋盤進行編號0~63，紙片位置可以用一個6位2進位數D表示，將硬幣正面視為1反面視為0，棋盤整除2位置上1的個數的奇偶代表D的第一位（例如，個數若為奇數則該位為1，反之則為0），棋盤除4餘0或餘1位置上1的個數的奇偶代表第二位，棋盤y除8餘0，1，2，3位置上1的個數的奇偶代表第四位，以此類推。

我們改變棋盤編號為0位置上的數字則D的6個二進位位都會改變（代表特定位置上1的個數的奇偶性發生改變），改變1號位置則除了第一位以外的二進位位都會改變，以此類推，顯然我們可以改變棋盤上的一個特定位置的0，1來改變這個6位2進位數使它成為0~63中任意數字，所以囚犯A可以只改變一枚硬幣使得D為紙片所在格的編號，而囚犯B只需計算D即可得到紙片位置。

這個問題我跟系友們進行了一個討論，得出了一個解，但我直觀上覺得這個解不一定「存活概率最高「（雖然存活概率已經足夠高）。

等大家討論後我再公布。

思路(下面提到的加法都是二進位異或加法)：

1.把紙條位置信息看成6行1列矩陣（列矢量）p，存放到針對這個64行1列的硬幣狀態信息矩陣x, 的一個運算結果里。設囚犯A的那個64行1列的翻轉硬幣狀態信息矩陣為y(稀疏的，只有翻轉位為1)。

2.構造一個校驗矩陣H，讓H乘以x 得到紙條位置信息p。

毫無疑問 H必須是6行64列的，而且在二進位異或加法下行線性無關的。

但是只能翻轉x的1bit，我們需要讓他翻轉不同的1bit 能得到不同的Hx。換而言之，我們需要設計一個

能糾正必然發生一位bit錯誤的，64位碼長的，校驗位為6個的信道糾錯碼，H是它的校驗矩陣.

毫無疑問，（63, 57）漢明碼A 就有糾正可能發生一位bit錯誤的能力。我們需要把它變成

（64,58）能夠糾正必然產生1位錯誤的碼B。

漢明碼A 對應的校驗矩陣的63列是所有非全0的6bit列矢量的集合。幾乎不用動腦筋就該猜到（腦洞一下吧，所謂的科學家的直覺，靈光閃現...各種腦補）， B對應的校驗矩陣H應該把全0的列矢量加上去。H的問題解決了。

現在的問題還剩下尋找增量y使得，H(x+y)=p, 翻譯成解碼問題就是：

尋找錯誤y使得，Hy=p+Hx

注意H中的列矢量已經包含了所有6bit列矢量，所以只需要查找一下p+Hx是H的哪一列然後翻轉x的對應列的bit就可以了。

綜上，編碼和解碼過程如下：

囚犯A計算p+Hx是H的哪一列，然後翻轉x的對應列的bit就可以了。

囚犯B計算H(x+y)=Hx+p+Hx=p 就得到了紙條位置信息p。

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

仔細對比了一下，這就是楊帆的方法（以及另外一位匿名用戶進行詳細解釋的方法），我的H乘法操作就對應匿名用戶的」所有向下硬幣位置的和「，而且他尋找的其它n長的問題本質就是在已知發生1位比特位錯誤時的解碼錯誤率問題。從信道編碼來看，n不是2次冪的話，是無法100%糾錯的。這時候相當於有一些信道錯誤，始終會和其它信道錯誤混淆，需要囚徒B去猜到底是什麼錯誤了。。。碼構造的好，這樣的錯誤率會低，但是對於其它碼長目前似乎沒有所謂的最好的」完美碼「出現喔。