作者terrorlone (愛摺紙的村哥)
看板puzzle
標題[問題] 近乎不可能的西洋棋盤謎題
時間Mon Mar 17 11:16:08 2025
這個問題一般的說法是出自 2020 年的一個 YouTube 影片，
也已經有幾年的歷史了，不過最近在臉書上又有一些相關的討論，
爬了一下似乎沒有人貼在這邊過，就順手貼一下。
題目：
獄長給兩個囚犯出了一個謎題。
兩個囚犯將會依序進入一個房間，
房間裡面有一個西洋棋盤（註：其方向是確定的，例如可以想像棋盤旁邊有寫座標），
棋盤的 64 個格子每個底下都是一個小收納空間，
其中恰有一個格子裡面藏了出獄的鑰匙，
而每一個格子上面都各放了一個硬幣，每個硬幣均可能是正面或反面。
第一個囚犯進入到房間之後，獄長會打開正確的格子讓他看鑰匙藏在哪一格裡面。
接下來，他唯一能做的事情就是把棋盤上其中一個格子的硬幣翻面
（且一定要翻一個），然後就必須離開房間、沒有機會傳遞其它訊息。
接著第二個囚犯進入到房間之後，他必須根據棋盤上的硬幣狀態來判斷出鑰匙藏在哪裡。
棋盤上的硬幣初始狀態會怎麼擺、以及鑰匙會藏在哪裡，都是無法事先知道的。
兩個囚犯之間的訊息傳遞，也僅限於第一個囚犯的翻面操作
（當然，第二個囚犯沒有任何方法知道第一個囚犯翻的是哪一個，
他只能看到翻面之後的全體狀態）。
不過兩個囚犯事前都完整地知道遊戲規則，他們可以盡情擬定策略。
難度（純屬個人見解）：★★★★☆
========================================
這個題目取名叫「近乎不可能的西洋棋盤謎題」、
就是因為兩個囚犯之間只能透過看似極少的操作、
來在龐大的解空間（64 * 2^64）裡面傳遞訊息。
但因為不是完全不可能，這謎題確實是有解的。
這幾年來在網路上解答這題的文章和影片一大堆，
但當然鼓勵各位自己解一遍。
這題我從看到題目開始在每天晚上邊想邊入睡，想了大概十天左右全部想出來。
要驗證各位的策略有效，一個簡單的方法就是寫程式來模擬整個過程，
如果編碼函數（第一個囚犯）和解碼函數（第二個囚犯）總是能正確合作，
那就對了～
一個不算提示的提示：不妨先考慮棋盤很小很小的情況，再試著推廣到 64 格。
順便一提：
這個謎題的可行策略當然不只一種，但可以證明，
所有的可行策略本質上都是等價的（只差在格子的排列與正反面的定義而已）。
--
▄
\ Terrorlone 西洋棋謎題專欄 為您獻上優質的精選謎題
▄
▄▄
\
▄ ▄
▄ \ 難度星級：1=3分鐘, 2=20分鐘, 3=2小時, 4=1天, 5=1週
▄ \ 推文請小心不要洩漏關鍵字，答對者敬請簽到 XD
▄
▄ \ 若覺得題意不清請盡量來信或水球詢問，不要用推的。
▄ \ 剛入門者可先閱讀
#19x4xedc、
#19y39PSk、
#1A1TgpvR ▄
\ 等等幾篇文章。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.161.71 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/puzzle/M.1742181374.A.AC7.html
※ 編輯: terrorlone (49.216.161.71 臺灣), 03/17/2025 11:23:08
1F：推 isnoneval: 推，這題能自己想出來的都是強者 03/17 23:50
2F：推 CHOIP: 有趣！剛推導 n= 2 4 8 有簡單策略 但還沒想出64通解 03/19 18:03
3F：→ terrorlone: 要進一步深刻思考那些比較小的解之所以可行的本質理 03/19 20:14
4F：→ terrorlone: 由所在 03/19 20:14
5F：推 CHOIP: 找到2進位排列通解了 n不是2的次方數也能套用 03/20 09:04
6F：推 CHOIP: 原理相同 解法不唯一…有空再分享我的版本及idea 03/20 09:07
7F：→ terrorlone: 咦？可是這題當 n=3 的時候應該是無解的…… 03/20 13:52
8F：推 CHOIP: n=3可解 總共只有8種可能 必能定義區分出3類型 03/20 18:15
9F：推 CHOIP: 舉個簡單的 只需觀察前2個 00為a 01為b 10和11都代表c 03/20 18:29
10F：推 CHOIP: 抱歉…上面不夠精確 03/20 18:32
11F：→ CHOIP: 010與011代表a 100與101代表b 其餘為c 03/20 18:34
12F：推 CHOIP: sorry 我想錯了…3真的無解…你說的才對 n要為2次方 03/20 18:40
13F：→ terrorlone: 基本上易看出：如果兩個佈局剛好只差兩個硬幣的正反 03/20 20:37
14F：→ terrorlone: ，那它們必然要屬於不同的「類」。由此很容易證明，n 03/20 20:37
15F：→ terrorlone: =3 的情況怎樣都至少會跑出四個類，而無法分成三類， 03/20 20:37
16F：→ terrorlone: 因此無解 03/20 20:37
17F：推 aragorn747: 第一直覺把隨便一格與有鑰匙那格同面的硬幣翻面到有鑰 03/20 21:25
18F：→ aragorn747: 匙那格，這樣不就，這樣不就解了？ 03/20 21:25
19F：推 DreamYeh: 我一直是3x1x數學頻道的鐵粉 所以你知道的...跳過XD 03/20 23:27
20F：→ DreamYeh: 另外給樓上 翻面完當然要放回同一格...否則就不是問題了 03/20 23:28
21F：→ terrorlone: 樓上沒自己解一遍？話說這題我自己解完之後我粗略翻 03/21 07:08
22F：→ terrorlone: 了幾篇解答文章，都覺得「怎麼寫那麼長」，我自己的 03/21 07:08
23F：→ terrorlone: 解法解釋起來用不到他們三分之一的篇幅就夠了（而且 03/21 07:08
24F：→ terrorlone: 當然程式驗證過的） 03/21 07:08
25F：推 DreamYeh: 我嘗試寫看看好了 03/21 08:12
