【組合】看似解不開的棋盤遊戲

張貼日期：Jan 20, 2025 4:10:15 AM

YouTube上有一個很受歡迎的數學科普頻道3Blue1Brown，主持人桑德森（Grant Sanderson）曾經介紹過一種西洋棋盤上的遊戲，標題是「無解的棋盤謎題」（The impossible chessboard puzzle，https://www.youtube.com/watch?v=wTJI_WuZSwE）。如果遊戲真得無解，也就有些乏味了。其實是看似無解，但經過仔細思考後，便有機會尋得巧妙解法。

遊戲的布局如下：【某位典獄長有一個特製的 8（橫）列 8（直）行（簡記為 8x8）共 64 格的西洋棋盤，每個方格都可掀開在下面藏匿小物件。典獄長把迷你鑰匙藏在他挑選的某個方格之下，又在盤面上放好 64 個硬幣，並且隨意選擇硬幣的正面或反面朝上。現在他請你進入室內，展示給你看哪個方格底下有鑰匙。之後，你必須翻轉而且只翻轉一個硬幣，接著你出去讓你的朋友進入室內，請他猜鑰匙藏在哪個方格底下。猜對了，你們就可以走出監獄，重新得到自由。】

一旦遊戲開始，你和你的朋友不准用任何方式交換訊息，不過事先你們已經被告知遊戲的規則，並且獲准商量妥當解密的方法。

現在問題來了：你和你的朋友有沒有一套策略，使得典獄長無論在哪一格藏鑰匙，也無論如何安排硬幣正反面，你都可以適當翻轉某一硬幣，使得你的朋友必定正確指出藏匿鑰匙的方格？

喜歡接受謎題挑戰的讀者，不妨在繼續閱讀下文之前，先來動動腦筋，看能不能想出解謎對策？

因為藏鑰匙與安排硬幣正反面都是隨機的，但是居然只靠翻轉一個硬幣便能傳達關鍵訊息，好像有點匪夷所思。因此拆穿這個棋盤遊戲的秘密，既引人入勝又具備困難度。

如果你在尋找致勝策略的過程中，一時感覺沒頭緒，也許應該把問題規模縮小，先嘗試解決較小棋盤上同性質的問題。因為 8 是 2 的 3 次方，我們可以先試試 2 的更小次方的棋盤。2 的 0 次方是 1，只有一個格子的棋盤，迷你鑰匙必在其下，不需要任何策略。所以第一個值得思考的情況是 2 x 2 的棋盤。

首先，我們需要選擇一種記錄題目中各種要素的方法，以便協助推理順利進行。因為有兩種展現硬幣的選擇，我們不妨約定好用 0 代表反面、1 代表正面，也就是說我們採用二進位數表示硬幣狀態。因此，我們也準備採用二進位數來表示棋盤方格的位置。下圖是 2 x 2 的棋盤。用 0 與 1 分別標出列與行的（十進位數）標號。

那麼每個方格可以依照由左至右的次序，寫入列標號的二進位數與行標號的二進位數（目前例子裡，0與1的二進位數仍然是0與1），從而列出一個由 0 與 1 構成的所謂二元序列（稱為位置標號），如下圖：

每個二元序列從左至右稱為第 1 位元、第 2 位元，現在再加入第 3 位元，代表放在那個方格的硬幣。例如下圖表示除了右上角方格放的是反面，其他方格放的都是正面。最後我們指定隱藏鑰匙的方格（稱為目標方格），是二元序列為111的右下角（用綠色突出顯示）。如此棋盤遊戲的一個實例已經設定完成。

下面是一種保證你的朋友能從棋盤布局讀出目標方格的策略，其步驟如下：

為什麼執行以上設定的三步驟之後，總能讀出正確答案呢？

讓我們來分析一下。

首先，我們注意到位置標號的一種特性。因為二元序列每個位元的值非 0 則 1，所以長度 2 的二元序列總共就只有 22 = 4 個。我們所賦予的位置標號，恰好窮盡了這 4 個可能的變化。這也保證在定位階段得到的 c1c2 一定會是某個位置標號。

其次，讀碼過程把位置標號與棋盤上硬幣的正反面布局關聯起來，此時位置標號扮演了記錄奇偶性的第二種功能。

重點是只有當位置標號裡的位元與最高位元同時為 1 時，翻轉才會對奇偶性發生作用。

例如在 2 x 2 的棋盤中，如果我們翻轉位置標號為 00 的硬幣之後再讀碼，則 x1 與 x2 的值是不會改變的。若翻轉位置標號為 01（或 10）的硬幣之後再讀碼，則只有 x2（或 x1）的值會改變；若翻轉位置標號為 11 的硬幣之後再讀碼，則 x1 與 x2 的值都會改變。
因此 x1 與 x2 的四種可能的變化，都得以經過翻轉某個硬幣而達成。

下面用定位獲得的 c1c2 來重新說明這個道理，以便後面可以推廣到更大的棋盤。

結論：經過翻轉位置標號 c1c2 的最高位元，再次讀碼的結果必定是隱藏鑰匙的正確位置。

 
以上 2 x 2 的棋盤看似簡單，但是我們設計的解謎策略以及正確性的論證，其實已經包容了適用於 2n x 2n 棋盤的通則。我們再舉 4 x 4 棋盤的例子(如下圖)。
為方便閱讀，下圖中列與行的號碼為 0, 1, 2, 3，它們的二進位數表示法為 00, 01, 10, 11，棋盤中前 4 位元分別用這些二進位數寫出列與行的號碼。第 5 位元表示硬幣的正反面，而第 4 列第 2 行的位置設定為目標位置。

我們再看一個 8 × 8 棋盤的例子，如下圖，目標位置設定在第 3 列第 6 行：

令 n 為正整數，我們已經通過實例解謎了 n = 1, 2, 3 時，2n × 2n 棋盤上的遊戲。
其實 n = 1 的情形就足夠有代表性，讓我們把解謎的策略自然地推廣到一般 n 的情形。此時我們有一個 2n × 2n 的棋盤，用 0, 1, .. . . n - 1 把列與行編以號碼。棋盤中每個方格裡有一個長度為 2n + 1 的二元序列。前 n 個位元是列號碼的二進位數表示法，接著 n 個位元是行號碼的二進位數表示法，第 2n + 1 位元代表硬幣的正反面（0 是反面、1 是正面）。最後選定某個方格為目標方格，令 t1t2 . . . t2n 表示目標方格的前 2n 個位元，也就是它的位置標號。

參加遊戲的第一位依照以下步驟，翻轉某個方格的最高位元：

以上這個推廣到 2n × 2n 棋盤的程序之所以正確，一方面是因為 2n × 2n = 22n，從而棋盤方格恰好容納了所有長度為 2n 的位置標號。另方面，我們除了讓參數 i 從 1 跑到 2n之外，其他論證步驟都仿照 n = 1 的情形，就可保證解謎方法能達成目標。

從解開這個看似無解的棋盤遊戲，我們學得一項寶貴的經驗，就是不要輕忽最簡單的情形。先嘗試解決最簡單的情形，也許就已經掌握了解謎的關鍵。

【致謝】：感謝我的高中同班同學林留玉仁將此謎題介紹給我，並且提供改善初稿的意見。