[問題] 近乎不可能的西洋棋盤謎題
看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者terrorlone (愛摺紙的村哥)時間2周前 (2025/03/17 11:16)推噓11(11推 0噓 14→)留言25則, 5人參與討論串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
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
03/20 09:04, 5F
推
03/20 09:07,
1周前
, 6F
03/20 09:07, 6F
→
03/20 13:52,
1周前
, 7F
03/20 13:52, 7F
推
03/20 18:15,
1周前
, 8F
03/20 18:15, 8F
推
03/20 18:29,
1周前
, 9F
03/20 18:29, 9F
推
03/20 18:32,
1周前
, 10F
03/20 18:32, 10F
→
03/20 18:34,
1周前
, 11F
03/20 18:34, 11F
推
03/20 18:40,
1周前
, 12F
03/20 18:40, 12F
→
03/20 20:37,
1周前
, 13F
03/20 20:37, 13F
→
03/20 20:37,
1周前
, 14F
03/20 20:37, 14F
→
03/20 20:37,
1周前
, 15F
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
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
puzzle 近期熱門文章
3
11
PTT遊戲區 即時熱門文章