[問題] 近乎不可能的西洋棋盤謎題

[terrorlone (愛摺紙的村哥)]

這個問題一般的說法是出自 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://www.ptt.cc/bbs/puzzle/M.1742181374.A.AC7.html
※ 編輯: terrorlone (49.216.161.71 臺灣), 03/17/2025 11:23:08
推 isnoneval: 推，這題能自己想出來的都是強者
推 CHOIP: 有趣！剛推導 n= 2 4 8 有簡單策略 但還沒想出64通解
→ terrorlone: 要進一步深刻思考那些比較小的解之所以可行的本質理
→ terrorlone: 由所在
推 CHOIP: 找到2進位排列通解了 n不是2的次方數也能套用
推 CHOIP: 原理相同 解法不唯一…有空再分享我的版本及idea
→ terrorlone: 咦？可是這題當 n=3 的時候應該是無解的……
推 CHOIP: n=3可解 總共只有8種可能 必能定義區分出3類型
推 CHOIP: 舉個簡單的 只需觀察前2個 00為a 01為b  10和11都代表c
推 CHOIP: 抱歉…上面不夠精確
→ CHOIP: 010與011代表a 100與101代表b 其餘為c
推 CHOIP: sorry 我想錯了…3真的無解…你說的才對 n要為2次方
→ terrorlone: 基本上易看出：如果兩個佈局剛好只差兩個硬幣的正反
→ terrorlone: ，那它們必然要屬於不同的「類」。由此很容易證明，n
→ terrorlone: =3 的情況怎樣都至少會跑出四個類，而無法分成三類，
→ terrorlone: 因此無解
推 aragorn747: 第一直覺把隨便一格與有鑰匙那格同面的硬幣翻面到有鑰
→ aragorn747: 匙那格，這樣不就，這樣不就解了？
推 DreamYeh: 我一直是3x1x數學頻道的鐵粉 所以你知道的...跳過XD
→ DreamYeh: 另外給樓上 翻面完當然要放回同一格...否則就不是問題了
→ terrorlone: 樓上沒自己解一遍？話說這題我自己解完之後我粗略翻
→ terrorlone: 了幾篇解答文章，都覺得「怎麼寫那麼長」，我自己的
→ terrorlone: 解法解釋起來用不到他們三分之一的篇幅就夠了（而且
→ terrorlone: 當然程式驗證過的）
推 DreamYeh: 我嘗試寫看看好了