鋸木板遊戲（The Game of Sawing planks）

Posted on 2011/07/19 in 排列組合, 數學 with 沒有迴響 6,421 views

鋸木板遊戲（The Game of Sawing planks）
國立台中女中數學科賴信志老師/國立台灣師範大學數學系許志農教授責任編輯

鋸木板遊戲源自於許志農教授戲說數學中的一個遊戲，規則如下：給一塊畫有 $$5\times 5$$ 或 $$6\times 6$$ 方格的木板，兩位玩家輪流切割一個單位的長度，先將木板鋸成兩塊者輸。

這個遊戲的必勝策略可由圖論中的「漢米爾頓路徑」(Hamiltonian path)加以解決。首先我們先定義有限平面鑲嵌圖形的「內交點」：扣除外圍邊界上的交點，剩餘的內部交點。如下圖就是一個 $$5\times 5$$ 的正方形平面鑲嵌圖形的內交點。

接著我們只要任意找到一條連接所有內交點的漢米爾頓路徑，再將這條路徑進行「連」與「不連」的必勝路徑設計。如下圖就是 $$5\times 5$$ 的正方形平面鑲嵌圖形的一條漢米爾頓路徑和必勝路徑設計。

顯然 $$5\times 5$$ 的鋸木板遊戲中，後手一定永遠可以鋸到必勝路徑中的紅色線段，此時後手所切割的線段必保持在圖形內部，且無法為成一封閉圖形，即無法將圖形分割為兩部分，所以後手有必勝策略。

這樣的方式可以推廣到 $$m\times n$$ 的矩形木板，因為我們可以輕易找到通過所有內交點的漢米爾頓路徑，再將此路徑進行「連」與「不連」的必勝路徑設計，而這樣的必勝路徑大概又可以分成兩類：一類是當內交點數為偶數時，必勝路徑會如上面 $$5\times 5$$ 的例子，形成間隔的線段；另一類則是當內交點數為奇數時，必勝路徑會間隔的線段再加上一個點。下圖就是 $$6\times 8$$ 矩形木板的漢米爾頓路徑和必勝路徑設計的例子：

在上圖的例子中，顯然先手一定可以先鋸到多出來的「一點」，接著永遠都能鋸到必勝路徑中的其他線段，所以先手有必勝規則。

接著我們把這個問題推廣到其他平面的正鑲嵌的圖形，也就是正三角形和正六邊形的平面正鑲嵌，我們一樣可以利用尋找漢米爾頓路徑的方式來設計必勝路徑，但我們必需先規定這兩種正鑲嵌圖形的生長規則，下圖分別是邊長為6 的正三角形和邊長為3 的正六邊形平面正鑲嵌木板中的漢米爾頓路徑及必勝路徑的例子。

一、正三角形的平面正鑲嵌(邊長為6)：

二、正六邊形的平面正鑲嵌(邊長為3)：

我們繼續將這問題推廣至以不同正多邊形在平面上密舖而成的半正鑲嵌圖形。它的規定是：每個內交點的組態必須相同，即其四周所圍繞的正多邊形有固定種類、個數和順序。

若一圖案上每個頂點依序是由正 $$1n$$ 邊形、正 $$2n$$ 邊形、正 $$3n$$ 邊形乃至正 $$kn$$ 邊形所拼合而成的，我們稱這樣鑲嵌的圖形為 $$\Box(n_1,n_2,n_3,…,n_k)$$，因此半正鑲嵌圖形共有如下 $$8$$ 種：$$\Box(3,12,12)$$、$$\Box(4,6,12)$$、$$\Box(4,8,8)$$、$$\Box(3,6,3,6)$$、$$\Box(3,4,6,4)$$、$$\Box(3,3,3,3,6)$$、$$\Box(3,3,3,4,4)$$、$$\Box(3,3,4,3,4)$$。

接著我們必需規定這 $$8$$ 種半正鑲嵌圖形各自在平面上的生長規則，但是我們會發現，有些平面半正鑲嵌的圖形可以利用找尋漢米爾頓路徑的方式來製造必勝路徑，但有些並不行，例如下面就以 $$\Box(3,3,4,3,4)$$ 和 $$\Box(4,8,8)$$ 的例子加以說明。

一、$$\Box(3,3,4,3,4)$$：
先定義其生長規則如下圖：

則以 $$n =4$$ 為例的漢米爾頓路徑和必勝路徑設如下：
二、$$\Box(4,8,8)$$：
先定義其生長規則如下圖：