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

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者 (愛摺紙的村哥)時間2周前 (2025/03/17 11:16), 2周前編輯推噓11(11014)
留言25則, 5人參與, 1周前最新討論串1/1
這個問題一般的說法是出自 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

03/17 23:50, 2周前 , 1F
推,這題能自己想出來的都是強者
03/17 23:50, 1F

03/19 18:03, 1周前 , 2F
有趣!剛推導 n= 2 4 8 有簡單策略 但還沒想出64通解
03/19 18:03, 2F

03/19 20:14, 1周前 , 3F
要進一步深刻思考那些比較小的解之所以可行的本質理
03/19 20:14, 3F

03/19 20:14, 1周前 , 4F
由所在
03/19 20:14, 4F

03/20 09:04, 1周前 , 5F
找到2進位排列通解了 n不是2的次方數也能套用
03/20 09:04, 5F

03/20 09:07, 1周前 , 6F
原理相同 解法不唯一…有空再分享我的版本及idea
03/20 09:07, 6F

03/20 13:52, 1周前 , 7F
咦?可是這題當 n=3 的時候應該是無解的……
03/20 13:52, 7F

03/20 18:15, 1周前 , 8F
n=3可解 總共只有8種可能 必能定義區分出3類型
03/20 18:15, 8F

03/20 18:29, 1周前 , 9F
舉個簡單的 只需觀察前2個 00為a 01為b 10和11都代表c
03/20 18:29, 9F

03/20 18:32, 1周前 , 10F
抱歉…上面不夠精確
03/20 18:32, 10F

03/20 18:34, 1周前 , 11F
010與011代表a 100與101代表b 其餘為c
03/20 18:34, 11F

03/20 18:40, 1周前 , 12F
sorry 我想錯了…3真的無解…你說的才對 n要為2次方
03/20 18:40, 12F

03/20 20:37, 1周前 , 13F
基本上易看出:如果兩個佈局剛好只差兩個硬幣的正反
03/20 20:37, 13F

03/20 20:37, 1周前 , 14F
,那它們必然要屬於不同的「類」。由此很容易證明,n
03/20 20:37, 14F

03/20 20:37, 1周前 , 15F
=3 的情況怎樣都至少會跑出四個類,而無法分成三類,
03/20 20:37, 15F

03/20 20:37, 1周前 , 16F
因此無解
03/20 20:37, 16F

03/20 21:25, 1周前 , 17F
第一直覺把隨便一格與有鑰匙那格同面的硬幣翻面到有鑰
03/20 21:25, 17F

03/20 21:25, 1周前 , 18F
匙那格,這樣不就,這樣不就解了?
03/20 21:25, 18F

03/20 23:27, 1周前 , 19F
我一直是3x1x數學頻道的鐵粉 所以你知道的...跳過XD
03/20 23:27, 19F

03/20 23:28, 1周前 , 20F
另外給樓上 翻面完當然要放回同一格...否則就不是問題了
03/20 23:28, 20F

03/21 07:08, 1周前 , 21F
樓上沒自己解一遍?話說這題我自己解完之後我粗略翻
03/21 07:08, 21F

03/21 07:08, 1周前 , 22F
了幾篇解答文章,都覺得「怎麼寫那麼長」,我自己的
03/21 07:08, 22F

03/21 07:08, 1周前 , 23F
解法解釋起來用不到他們三分之一的篇幅就夠了(而且
03/21 07:08, 23F

03/21 07:08, 1周前 , 24F
當然程式驗證過的)
03/21 07:08, 24F

03/21 08:12, 1周前 , 25F
我嘗試寫看看好了
03/21 08:12, 25F
文章代碼(AID): #1drvF-h7 (puzzle)
文章代碼(AID): #1drvF-h7 (puzzle)