中 華 民 國 第 四 十 五 屆 中 小 學 科 學 展 覽 會 作 品 說 明 書 高 中 組 數 學 科 040420 棋 盤 上 的 馬 步 臺 北 市 立 麗 山 高 級 中 學 作 者 姓 名 : 高 二 黃 右 嫺 高 二 潘 建 融 高 二 陳 柏 諺 指 導 老 師 : 黃 靜 寧
中 華 民 國 第 四 十 五 屆 中 小 學 科 學 展 覽 會 作 品 說 明 書 科 別 : 數 學 科 組 別 : 高 中 組 作 品 名 稱 : 棋 盤 上 的 馬 步 關 鍵 詞 : 棋 盤 馬 步 漢 米 爾 頓 編 號 :
目 錄 壹 摘 要 P.2 貳 研 究 動 機 P.2 參 研 究 目 的 P.2 肆 研 究 設 備 及 器 材 P.2 伍 研 究 方 法 P.3 陸 研 究 結 果 與 討 論 P.6 柒 結 論 P.25 捌 參 考 資 料 P.26-1 -
壹 摘 要 棋 盤 上 的 馬 步 馬 步 的 走 法 有 八 種, 下 面 我 們 討 論 以 馬 步 不 重 複 地 一 次 走 完 整 個 棋 盤 的 可 行 性, 已 證 明 出 的 結 果 如 下 : 一 在 n m 的 矩 陣 中, 除 3 3,3 5,3 6 和 4 4 為 無 解 外, 其 餘 的 我 們 已 證 出 均 至 少 有 一 解 二 在 n m 均 大 於 4 且 n m 為 偶 數 時, 可 以 以 任 一 格 為 起 點 三 在 n m 均 大 於 4 且 n m 為 奇 數 時, 可 以 以 套 色 後 格 數 多 一 格 的 顏 色 格 子 為 起 點 四 對 於 無 解 的 矩 陣, 我 們 改 以 虧 格 的 形 式 討 論, 也 找 出 虧 格 在 適 當 位 置 時 可 有 解 的 情 形 五 有 虧 格 的 大 矩 陣, 在 總 格 子 數 為 偶 數 時, 可 以 以 任 一 格 為 起 點 ; 總 格 子 數 為 奇 數 時, 可 以 任 一 套 色 後 格 數 多 一 格 的 顏 色 格 子 為 起 點 貳 研 究 動 機 在 高 一 的 數 學 研 究 方 法 課 程 中, 配 合 整 數 單 元 我 們 曾 經 討 論 過 奇 數 與 偶 數 的 主 題 當 時, 我 們 討 論 下 面 的 問 題 : 一 在 中 國 象 棋 的 棋 盤 上, 馬 能 否 從 某 些 點 出 發, 可 以 不 重 複 地 跳 遍 半 個 棋 盤 ; 而 從 另 外 一 些 點 出 發, 卻 不 能 完 成 ( 這 與 高 二 下 排 列 組 合 中 是 否 有 一 筆 劃 路 徑 的 課 程 相 關 ) 圖 1 中, 半 個 棋 盤 裏, 紅 點 有 22 個, 藍 點 有 23 個, 若 馬 步 由 紅 點 開 始, 下 一 步 必 須 走 到 藍 點, 很 明 顯 的 最 後 會 有 一 個 藍 點 落 單, 無 法 完 成 馬 步 走 完 半 個 棋 盤, 所 以 必 須 由 藍 點 出 發 圖 1 二 上 述 的 題 目, 加 上 跳 回 原 出 發 點 的 條 件, 其 結 果 會 有 什 麼 不 同 呢? 三 前 列 兩 題, 題 中 的 半 個 棋 盤 若 改 為 整 個 棋 盤 情 況 又 將 如 何? 參 研 究 目 的 一 討 論 在 n m 的 矩 陣 中 是 否 能 有 馬 步 路 徑 的 解? 二 討 論 有 解 的 n m 矩 陣 中 有 哪 些 格 子 可 做 起 點, 哪 些 不 行? 三 討 論 在 無 解 的 矩 陣 中 有 一 虧 格 時 能 否 有 解? 四 討 論 大 的 矩 陣 中 有 一 虧 格 時 的 情 況 肆 研 究 設 備 及 器 材 人 腦 紙 筆 電 腦 Microsoft Visual FoxPro5.0 Dev-C++4 Visual Basic 6.0 GP4.03-2 -
伍 研 究 方 法 一 文 獻 探 討 ( 一 ) 漢 米 爾 頓 路 徑 與 迴 圈 給 一 圖 G( 圖 2), 以 V 來 表 示 所 有 頂 點 的 集 合,E 表 示 所 有 邊 的 集 合, 記 成 G=(V,E), 通 過 途 中 的 每 一 頂 點 且 只 通 過 一 次 的 路 徑 稱 為 漢 米 爾 頓 路 徑 ; 若 是 要 求 必 須 再 回 到 起 始 頂 點 的 回 路, 則 稱 為 漢 米 爾 頓 迴 圈 ( 如 圖 3) 圖 2 圖 3 ( 二 ) 古 人 研 究 十 八 世 紀 時 歐 拉 提 出 了 是 否 能 用 騎 士 一 次 走 完 整 個 西 洋 棋 的 棋 盤 而 不 重 複? 開 始 了 大 家 對 騎 士 走 8 8 棋 盤 之 討 論 我 們 查 閱 了 不 少 書 藉 雜 誌 和 網 路 資 料, 但 大 部 份 均 為 尋 找 解 的 個 數 之 討 論, 如 數 學 傳 播 季 刊 10 卷 2 期 林 建 宏 所 寫 的 5 階 棋 盤 之 騎 士 漫 遊 僅 有 112 個 解, 是 用 電 腦 程 式 找 出 所 有 解 ;28 卷 3 4 期 中 林 克 瀛 所 寫 的, 騎 士 漫 遊 方 陣 與 魔 方 陣 六 階 棋 盤 上 的 騎 士 迴 圈 漫 遊 共 有 1245 種, 則 是 以 推 論 方 式 得 證 解 的 個 數 這 些 資 料 中 對 小 矩 陣 之 情 況 有 豐 富 的 探 討, 但 不 見 其 對 不 同 棋 盤 中 是 否 能 有 解, 或 可 有 解 之 情 形 的 證 明 與 討 論 二 定 義 ( 一 ) 方 陣 行 數 列 數 相 同 的 方 格 圖 ( 二 ) 矩 陣 行 數 列 數 不 等 的 方 格 圖 ( 三 ) 關 鍵 矩 陣 連 接 數 個 矩 陣 時 最 重 要 的 矩 陣 ( 例 : 圖 18) 三 找 馬 步 矩 陣 解 的 方 法 若 將 此 類 方 格 換 成 點, 把 馬 步 用 線 來 取 代, 則 要 找 的 解 就 是 一 個 漢 米 爾 頓 路 徑 或 迴 圈, 但 要 確 定 此 圖 形 是 否 有 漢 米 爾 頓 路 徑 或 迴 圈 是 個 很 困 難 的 問 題 所 以, 我 們 運 用 下 面 幾 種 找 解 的 方 法, 做 為 找 較 大 矩 陣 的 解 或 推 理 到 n m 時 必 用 的 武 器, 下 面 是 我 們 在 研 究 過 程 中 運 用 的 幾 種 基 本 方 法 ( 一 ) 迴 圈 法 先 找 出 方 格 中 的 迴 圈, 通 常 是 以 兩 層 為 一 圈 ( 如 圖 4), 再 設 法 連 接 各 迴 圈 例 :5 5 與 9 9 均 可 用 迴 圈 法 輕 鬆 的 找 到 一 解 圖 5 圖 4 圖 6 迴 圈 法 在 方 陣 時 很 容 易 使 用 且 可 推 廣 至 n n 的 情 況, 但 矩 陣 卻 是 它 的 剋 星, 原 因 是 中 間 剩 下 的 格 子 會 隨 著 不 同 矩 陣 而 變 化, 非 常 難 掌 握 - 3 -
( 二 ) 橋 數 法 馬 步 有 八 個 方 向, 也 就 是 在 方 格 中 橋 數 最 多 為 8, 但 在 方 格 邊 緣 或 有 的 位 置 已 被 前 面 的 步 占 掉 時 橋 數 就 會 小 於 8 因 此 在 找 解 時 我 們 通 常 會 由 橋 數 較 小 的 開 始, 而 遇 到 有 兩 個 以 上 的 橋 可 選 擇 時 則 選 橋 數 小 的 先 走 ( 如 圖 7) 例 : 圖 7 圖 8 圖 8 為 3 4 的 矩 陣 以 橋 數 法 找 解 的 過 程, 圖 中 紅 色 框 中 的 數 位 為 選 中 該 格 後 下 一 步 的 橋 數, 而 在 遇 到 有 兩 格 以 上 橋 數 都 最 小 時, 任 意 選 其 中 一 格 走 另 外, 我 們 也 寫 了 一 個 程 式 顯 示 下 一 步 或 所 有 格 子 的 橋 數, 在 無 其 他 的 限 制 條 件 時, 依 橋 數 法 的 規 則 走 幾 乎 都 可 找 到 解, 非 常 好 用 但 若 有 限 制 條 件, 如 : 固 定 起 點 和 終 點, 則 必 須 靠 下 面 的 方 法 幫 忙 才 容 易 找 到 需 要 的 解 ( 三 ) 前 後 呼 應 法 有 時 我 們 會 需 要 固 定 起 點 和 終 點 的 解, 或 是 比 較 特 殊 的 方 格 直 接 從 頭 開 始 找 會 很 不 容 易 ( 有 可 能 是 無 解 ), 這 時 除 了 從 頭 開 始 找, 我 們 也 會 從 結 束 點 倒 推 回 來 發 現 頭 尾 無 法 連 接 則 無 解, 找 到 頭 尾 相 接 則 得 到 一 解 例 : 若 想 要 找 3 4 矩 陣 符 合 圖 9,( 起 點 ) 與 E( 終 點 ) 的 解, 則 1 到 4 步 因 為 都 只 有 一 條 橋 可 以 選, 所 以 走 法 如 圖 9 而 圖 9 到 第 5 步 時 有 兩 個 選 擇 ( 圖 9 中 紅 框 ), 這 時 換 從 終 點 走 回 來 會 發 現,12 倒 著 走 只 能 走 到 圖 中 11 的 位 置, 但 走 到 11 後 就 沒 有 橋 可 繼 續 走, 所 以 得 證, 在 3 4 的 矩 陣 中 無 法 有 符 合 圖 中 與 E 的 路 徑 ( 四 ) 先 分 割 後 連 接 法 在 比 較 大 的 矩 陣 不 太 可 能 用 前 面 的 方 法 慢 慢 的 找, 所 以 在 大 的 矩 陣 或 在 要 推 證 到 n m 時, 我 們 將 大 矩 陣 分 割 成 小 矩 陣, 再 利 用 小 矩 陣 間 的 連 接 加 以 完 成 圖 10 例 : 將 3 8 的 矩 陣 先 分 成 兩 個 3 4 的 矩 陣, 即 圖 10 的 紅 色 矩 陣 和 藍 色 矩 陣, 因 為 走 完 紅 色 矩 陣 後 在 12 的 位 置 剛 好 可 與 藍 色 矩 陣 的 1 連 接, 所 以 只 要 再 把 藍 色 矩 陣 走 完 就 得 到 了 3 8 矩 陣 的 一 組 解 若 使 用 這 種 方 法 多 接 幾 個 矩 陣, 一 直 延 伸 下 去, 就 可 用 來 證 明 n m 時 的 情 況 所 以, 此 種 方 法 雖 對 小 的 矩 陣 沒 有 用, 但 在 尋 找 通 解 時 卻 不 能 沒 有 它 ( 五 ) 電 腦 找 解 法 我 們 將 棋 盤 座 標 化, 以 橫 坐 標 與 縱 坐 標 的 加 減 來 表 示 馬 步 移 動 後 的 座 標 用 電 腦 依 序 判 斷 每 一 步 的 八 個 方 位 是 否 超 出 棋 盤 範 圍 或 已 經 走 過, 通 過 判 斷 的 就 繼 續 走 下 一 步, 未 通 過 的 則 試 另 一 個 方 位, 若 全 部 未 通 過 則 倒 退 一 步, 繼 續 試 前 一 步 的 另 外 3 個 後 續 位 置, 直 到 找 出 所 有 可 能 的 解 ( 下 頁 中 的 圖 11 為 電 腦 找 解 法 之 程 式 的 流 程 圖 ) - 4 -
電 腦 找 解 法 之 程 式 的 流 程 圖 圖 11-5 -
陸 研 究 結 果 與 討 論 一 n m 矩 陣 與 馬 步 路 徑 ( 一 ) n=3 時 1. m=3 (3 3) 圖 12 中, 中 間 的 點 沒 有 橋, 故 3 3 的 方 陣 無 解 2. m=5 (3 5) 圖 12 圖 13 中, 有 3 5 矩 陣 中 的 所 有 點 和 幾 條 橋, 其 中 C E 的 橘 色 迴 圈 內 點 A B 必 有 一 為 起 點 或 終 點, 否 則 將 無 法 走 到 其 他 的 點, 因 此 點 C D E F 中 最 A B 多 只 能 再 有 一 個 點 做 起 點 或 終 點, 但 圖 中 有 一 點 有 四 條 橋,4-1=3 大 於 2, 所 以 3 5 的 矩 陣 是 無 解 的 D 圖 13 F 3. m=6 (3 6) 承 上 所 述 起 點 與 終 點 必 為 A 或 B 與 C 或 D 中 的 一 點, 但 此 兩 迴 圈 無 法 在 走 完 其 他 所 有 的 點 後 相 連, 所 以 3 6 的 矩 陣 是 A C B D 無 解 的 圖 14 4. 其 他 情 況 由 3 4 矩 陣 的 一 組 解, 用 連 接 法 連 接 k 個 相 同 的 矩 陣 ( 如 圖 15), 可 得 3 4k 矩 陣 的 一 組 解 而 同 理 可 證 m=4k+1,m=4k+2 和 m=4k+3 時 的 情 況 圖 15 ( 二 ) 方 格 為 4 m 時 因 為 4=2+2, 若 用 兩 格 環 繞 的 迴 圈 法, 中 間 剛 好 不 會 有 多 餘 的 格 子 干 擾, 所 以 我 們 就 以 這 種 方 法 分 兩 類 來 證 明 1. m=2c+3 且 c 1 圖 16 為 4 (4k+1) 時 的 情 形, 以 左 下 角 做 起 點 而 以 起 點 右 邊 一 格 為 終 點 的 一 組 解 而 4 (4k+3) 時 同 理 可 證 圖 16-6 -
2. m=2c+2 且 c 1 m=4k+2 的 情 形 比 m=4k+1 時 複 雜 的 多, 無 法 直 接 從 左 下 角 開 始 就 完 成, 不 過 我 們 發 現 將 此 四 個 迴 圈 若 依 下 面 順 序 連 接 A1-A2-C1-C2-D1-D2-B1-B2( 其 中 的 X1-X2 圖 17 為 以 X1 為 起 點 X2 為 終 點 的 方 式 走 X 迴 圈,X=A B C D) 則 剛 好 可 得 一 組 解 m=4k 時 與 此 類 似, 唯 k=1 時 為 無 解 ( 三 )n m 均 大 於 4 時 因 為 最 小 的 n n 馬 步 方 陣 為 5 5 的 方 陣, 所 以 在 n m=5 開 始 我 們 用 連 接 法 將 小 矩 陣 連 接 成 大 矩 陣 由 關 鍵 矩 陣 ( 圖 中 左 上 紫 色 之 矩 陣, 因 其 負 責 控 制 不 同 的 餘 數, 為 所 有 連 接 的 矩 陣 中 最 重 要 的 一 個, 故 在 此 稱 之 為 關 鍵 矩 陣 ) 的 不 同 大 小 可 把 n m 的 馬 步 方 陣 分 成 以 下 十 五 種 情 況 (p q 均 為 自 然 數, 且 p q 為 連 接 的 方 格 數 ):5p 5q, 5p (5q+1),5p (5q+2),5p (5q+3),5p (5q+4),(5p+1) (5q+1),(5p+1) (5q+2), (5p+1) (5q+3),(5p+1) (5q+4),(5p+2) (5q+2),(5p+2) (5q+3),(5p+2) (5q+4), (5p+3) (5q+3),(5p+3) (5q+4),(5p+4) (5q+4) 只 要 找 到 一 個 起 點 和 終 點 可 以 符 合 圖 中 紅 點 ( 起 點 ) 與 綠 點 ( 終 點 ), 即 可 由 圖 中 的 路 徑 得 到 (5p+1) (5q+2) 時 的 解, 其 它 十 四 種 情 況 亦 同 圖 18 只 有 在 兩 邊 幫 助 連 接 的 矩 陣 均 為 奇 偶 矩 陣 時, 因 為 此 類 矩 陣 之 結 束 點 不 能 在 X( 見 圖 19) 的 位 置 ( 因 為 開 始 點 和 結 束 點 的 顏 色 需 不 同 ), 無 法 用 之 前 的 連 接 方 式 一 次 證 明, 所 以 我 們 選 擇 用 E 做 結 束 點 將 其 分 成 每 列 奇 數 個 矩 陣 每 列 偶 數 個 矩 陣 來 討 論, 以 解 決 此 問 題 圖 19-7 -
1. 每 列 矩 陣 數 為 奇 數 圖 20 2. 每 列 矩 陣 數 為 偶 數 圖 21-8 -
二 n m 矩 陣 與 馬 步 迴 圈 我 們 希 望 知 道 在 馬 步 矩 陣 中, 除 了 可 以 有 至 少 一 解 外, 是 否 所 有 的 格 子 都 可 以 做 為 起 點? 或 是 哪 些 格 子 一 定 不 能 做 為 起 點? 又 若 在 矩 陣 中 找 到 一 漢 米 爾 頓 迴 圈, 則 可 確 定 此 馬 步 矩 陣 可 由 任 意 一 點 做 起 點 繞 此 迴 圈 而 結 束 在 此 起 點 的 前 或 後 一 點 無 解 的 方 陣 或 矩 陣 在 此, 則 不 予 討 論 ( 一 ) n m 為 奇 數 時 在 n m 為 奇 數 的 矩 陣 中, 定 義 : 將 相 鄰 的 格 子 塗 上 兩 種 不 同 的 顏 色 稱 為 套 色 ( 如 圖 22), 則 黃 格 會 比 藍 格 多 一 格 依 照 馬 步 走 法, 從 黃 格 只 能 走 到 藍 格, 而 藍 格 也 只 能 走 到 黃 格 假 設 從 黃 格 出 發, 此 格 所 有 的 橋 都 是 連 到 藍 格, 因 此 若 有 漢 米 爾 頓 迴 圈, 結 束 格 必 須 在 藍 格, 但 這 與 黃 格 會 比 藍 格 多 一 圖 22 格 應 結 束 在 黃 格 矛 盾, 所 以 在 奇 數 格 的 矩 陣 中 無 法 找 到 漢 米 爾 頓 迴 圈 又 若 從 藍 格 出 發, 一 定 會 有 至 少 一 個 黃 格 無 法 走 到, 所 以 也 無 法 從 藍 格 開 始 ( 二 ) n=3 時 1. 3 4 在 圖 23 中,A 這 個 位 置 只 有 兩 條 橋, 到 達 J 與 G 的 位 罝, 一 個 做 出 發 點 另 一 個 就 必 為 結 束 點, 可 以 任 意 選 擇 我 們 若 選 G 出 發, 只 能 走 到 I 再 接 B, 到 了 B 時 有 兩 個 選 擇 分 別 是 H K, 若 選 擇 H 的 話 就 只 能 再 接 到 J, 這 使 得 J 無 法 成 為 終 點, 而 選 擇 K 則 無 法 走 圖 23 到 H, 所 以 3 4 的 矩 陣 沒 有 馬 步 迴 圈 又 若 想 從 B 這 格 開 始 有 三 條 可 能 路 線, 可 走 B-I-G-A-J 但 之 後 若 走 H 則 無 法 繼 續, 若 不 走 H 則 H 就 永 遠 走 不 到 走 K-E 或 K-D 的 話, 結 束 點 就 一 定 要 在 I, 不 然 I 就 走 不 到 ( 因 為 I 只 剩 一 條 橋 ), 那 麼 反 過 來 由 I 往 回 走 I-G-A-J, 此 時 H 就 會 出 現 同 上 的 問 題, 所 以 無 法 完 成 綜 合 上 述 幾 點 及 前 面 得 到 的 解, 得 證 3 4 的 矩 陣 只 能 有 圖 中 綠 色 格 為 起 點 或 終 點 2. 3 8 圖 24 中, 從 1 開 始 的 話 則 A 和 B 必 須 分 別 是 出 發 點 和 結 束 點, 因 為 若 不 當 做 出 發 和 結 束 點 則 必 有 一 個 走 不 到 若 走 1-A-C 則 倒 回 來 走 一 定 是 B-D, 之 後 C 和 D 可 以 隨 意 選 走 X 或 Y 路 線 到 達 X 和 Y1 或 Y2, 此 時 必 接 右 邊 的 3 4 矩 陣, 圖 24 但 由 已 知 的 三 組 解 中 得 知 無 法 適 當 的 連 接 X 和 Y1 或 Y2, 所 以 3 8 的 矩 陣 無 法 以 1 或 2 的 位 置 為 起 點 或 終 點 又 由 已 知 解 中 得 知 其 餘 的 格 子 均 可 做 為 起 點 3. m=10+4k,k 1 時 圖 25 中, 已 知 3 10 的 馬 步 迴 圈, 由 16 為 起 點 15 為 終 點, 走 完 後 連 接 3 4 矩 陣 的 而 結 束 在 E, 因 為 E 可 以 再 迴 到 16, 所 以 得 到 3 14 的 一 個 馬 步 迴 圈 解 由 歸 納 法 可 得, 如 圖 26 中 大 矩 陣 的 位 置 只 有 兩 條 橋, 必 為 一 進 一 出, 所 圖 25 圖 26 以 只 要 有 迴 圈 的 解 即 可 把 做 為 起 點 E 當 做 終 點, 之 後 接 到 小 矩 陣 的 位 置, 而 走 - 9 -
已 知 的 路 徑 可 到 達 E, 且 因 為 E 可 以 再 回 到 出 發 點 的, 所 以 得 到 一 馬 步 迴 圈 的 解 4. m=12+4k,k 1 時 同 上 述 m=10+4k 的 解 法, 在 此 時 我 們 一 樣 先 找 出 3 12 的 馬 步 迴 圈 ( 如 圖 27), 之 後 用 歸 納 法 將 連 接 圖 27 的 矩 陣 無 限 延 伸, 而 得 到 一 馬 步 迴 圈 的 解 ( 如 圖 28) 圖 28 ( 三 ) n=4 時 圖 29 圖 30 同 4 4 無 解 的 證 明, 在 此 不 論 m 為 奇 數 或 偶 數, 若 將 格 子 套 色 如 圖 29 30 的 話, 橘 色 格 只 能 走 到 白 色 格, 而 若 想 要 有 迴 圈 就 必 須 橘 白 橘 白 的 走 才 有 可 能 但 圖 30 中, 藍 白 格 要 連 接 時, 必 須 於 圖 29 中 的 白 格 中 連 接, 所 以 得 證 不 可 能 有 迴 圈 同 理 可 知 若 想 要 完 成 4 m 的 矩 陣, 必 須 以 橘 色 格 為 起 點, 走 圖 30 中 的 同 色 格, 直 到 走 完 後 再 接 不 同 色 格 才 能 有 機 會 完 成 由 此 結 果 我 們 猜 測 若 起 點 為 圖 30 中 的 藍 格, 則 必 有 至 少 一 解, 且 終 點 的 位 置 在 任 一 白 格 與 圖 29 中 橘 格 交 集 之 格 子, 下 面 我 們 用 迴 圈 法 來 證 明 此 猜 測 1.m=2k+1,k 1 圖 31 中,A 迴 圈 在 中 間 兩 列 時 剛 好 都 可 以 走 到 白 格, 而 所 有 的 白 格 又 剛 好 是 一 個 迴 圈, 所 以 可 以 結 束 結 在 任 一 格 2.m=2k,k 3 圖 32 33 中, 分 別 為 兩 種 可 能 的 情 況, 均 是 有 兩 個 迴 圈 A B, 且 除 了 角 落 的 A B 外 均 可 互 換 ( 即 A 走 到 B 或 B 走 到 A), 所 以 不 論 從 哪 格 開 始 都 可 走 完 A 和 B 而 當 A B 圖 31 圖 32 圖 33 在 中 間 兩 列 時 剛 好 都 可 以 走 到 白 格, 所 以 此 時 可 完 成 所 以 格 而 結 束, 得 證 上 述 猜 想 另 外, 我 們 用 程 式 找 解 時 發 現 在 m 比 較 大 後, 任 一 個 前 面 證 出 有 解 的 點 開 始 時, 可 以 結 束 在 圖 30 中 一 四 列 與 起 點 不 同 色 的 格 子, 不 過 目 前 還 未 得 到 完 整 的 證 明 ( 四 ) n m 均 大 於 4 時 同 前 面 n m 路 徑 的 證 明, 這 一 部 份 我 們 也 是 用 連 接 法 來 證, 不 同 的 是 這 裡 需 要 考 慮 - 10 -
格 子 數 不 能 為 奇 數 和 p q 之 奇 偶 的 影 響 在 此 我 們 不 再 將 十 五 種 情 況 分 別 討 論, 而 只 考 慮 關 鍵 矩 陣 的 奇 偶 和 p q 的 奇 偶 來 證 明 1. 關 鍵 矩 陣 為 奇 奇 ( 圖 中 的 關 鍵 矩 陣 均 只 以 其 中 一 個 為 例, 其 它 情 況 可 依 此 類 推 ) (1) p 為 奇 數 q 為 偶 數 圖 34-11 -
(2) p q 均 為 偶 數 圖 35 2. 關 鍵 矩 陣 為 偶 奇 ( 奇 偶 與 偶 奇 互 為 對 稱, 因 此 可 以 看 為 一 組 ) (1) p 為 奇 數 q 為 偶 數 圖 36-12 -
在 此 若 p=1 或 q=1, 則 用 圖 36 之 繞 法 將 不 能 找 到 迴 圈, 所 以 我 們 用 類 似 3 m 時 的 證 法 來 補 上 p=1( 圖 37) 及 q=1( 圖 38) 時 的 證 明 圖 37 (2) p q 均 為 偶 數 圖 38 圖 39-13 -
(3) p q 均 為 奇 數 3. 關 鍵 矩 陣 偶 偶 (1) p 為 偶 數 q 為 奇 數 圖 40 圖 40 圖 41-14 -
偶 偶 的 情 形 在 p=1 或 q=1 時 也 無 法 從 上 圖 得 到 迴 圈, 因 此 以 圖 42 中 之 方 法 證 明 (2) p q 均 為 奇 數 圖 42 圖 43 三 n m 為 奇 數 時 的 解 前 面 我 們 已 用 簡 單 的 方 法 證 明 了 必 無 解 的 情 況, 但 尚 未 確 定 是 否 其 它 格 子 均 可 有 解 一 開 始 我 們 想 用 迴 圈 法 來 證 明, 但 此 種 方 法 只 適 用 於 方 陣 無 法 推 至 矩 陣, 且 證 明 方 法 複 雜 ; 後 來 我 們 又 試 著 用 上 面 n m 矩 陣 迴 圈 解 的 證 法, 但 由 於 5 為 奇 數, 無 法 推 證 到 所 有 格 子 最 後, 我 們 將 連 接 的 5 5 方 陣 改 為 偶 數 的 6 6 方 陣, 以 解 決 此 問 題, 且 因 為 六 為 偶 數 不 論 增 加 奇 偶 數 個, 整 個 大 矩 陣 仍 為 奇 奇, 也 就 可 以 不 用 考 慮 奇 偶 不 同 的 影 響 另 外 我 們 也 用 程 式 做 較 小 矩 陣 的 確 認 - 15 -
1. p 為 偶 數 圖 44 第 一 次 從 關 鍵 矩 陣 中 的 任 一 黃 格 為 起 點, 由 已 知 的 解 得 均 可 結 束 在 藍 點, 而 延 綠 色 箭 頭 的 方 向 走 ( 圖 44), 每 一 矩 陣 均 以 紅 點 開 始 藍 點 結 束 ( 從 已 知 解 得 知 可 完 成 ), 即 得 在 關 鍵 矩 陣 中 的 黃 格 出 發 均 可 完 成, 但 如 果 要 推 到 其 它 格 子 的 話, 會 受 奇 數 格 的 影 響 必 須 用 下 面 的 方 法 倒 著 走 回 去 圖 45 如 圖 45 左 中, 關 鍵 矩 陣 右 邊 的 矩 陣 中, 任 意 黃 格 開 始 均 可 結 束 在 藍 點, 則 可 以 繼 續 連 下 去, 只 有 在 連 接 路 線 碰 到 關 鍵 矩 陣 後, 奇 數 格 會 使 接 下 來 的 起 點 和 終 點 格 顏 色 改 變 ( 如 圖 45 右 ), 所 以 必 須 有 所 變 化, 不 過 均 可 延 此 一 規 則 延 伸 下 去 - 16 -
2.p 為 奇 數 圖 46 由 前 面 的 證 明 可 以 確 定 在 大 的 矩 陣 皆 可 完 成, 但 若 是 連 接 矩 陣 只 有 一 行 或 一 列 時 就 無 法 繞 回 前 面 那 個 迴 圈, 因 此 下 面 我 們 補 充 只 有 一 行 或 一 列 時 的 證 明 3. 3 m 5 m 7 m 9 m 時 我 們 找 到 小 矩 陣 中 若 以 藍 字 的 格 子 開 始 皆 可 以 結 束 在 紅 字 的 格 子, 則 由 前 面 的 證 明 我 們 可 以 確 定 後 面 不 論 再 接 多 少 個 3 4 矩 陣 皆 可 完 成 而 每 一 接 上 的 矩 陣 皆 可 依 圖 47 中 的 數 字 順 序 走 完 ( 遇 到 紅 或 藍 的 數 字 時 先 走 完 原 矩 陣 的 所 有 方 格 再 做 連 接 ), 所 以 不 論 m 為 多 少 時, 只 要 該 方 陣 是 有 解 的 即 得 由 黃 色 格 開 始 皆 有 解 而 5 m 7 m 9 m 時 也 可 以 相 同 方 式 證 明 圖 47-17 -
四 虧 格 條 件 在 前 面 我 們 討 論 了 所 有 完 整 的 矩 陣 的 情 況, 其 中 有 幾 個 較 小 的 矩 陣 是 無 解 的, 這 讓 我 們 想 到 若 將 棋 盤 改 為 虧 格 的 形 式 時 是 否 可 以 有 解? 答 案 是 肯 定 的! 下 面 我 們 先 說 明 可 有 解 時 的 條 件 : ( 一 ) 奇 數 格 的 矩 陣 中 虧 格 只 能 位 於 原 先 套 色 後 格 數 多 一 格 的 顏 色 格 子, 而 偶 數 格 的 矩 陣 則 任 一 格 均 可 做 為 虧 格 ( 二 ) 若 虧 格 位 置 在 原 矩 陣 中 是 可 當 起 點 的 格 子, 則 該 虧 格 矩 陣 至 少 必 有 一 馬 步 路 徑 解, 由 原 先 的 第 二 步 開 始 走 即 可 完 成 ( 三 ) 有 虧 格 的 矩 陣 中, 橋 數 為 1 的 格 子 須 做 為 起 點 或 終 點 ( 不 得 有 格 子 之 橋 數 小 於 1) 因 此 若 虧 格 造 成 有 兩 個 可 以 馬 步 連 結 的 格 子 或 任 三 個 以 上 的 格 子 橋 數 為 1 時, 該 矩 陣 將 無 法 完 成 ( 四 ) 若 有 虧 格 後, 使 圖 形 中 一 點 有 超 過 二 條 必 走 路 徑 ( 不 能 刪 的 橋 ), 則 必 無 法 完 成 ( 五 ) 在 找 解 的 過 程 中, 若 出 現 兩 個 格 子 只 有 1 條 橋, 則 必 須 先 走 其 中 一 格 且 須 以 另 一 格 為 終 點 ; 若 出 現 三 個 以 上 格 子 只 有 1 條 橋, 該 矩 陣 將 無 法 完 成 五 有 虧 格 的 矩 陣 與 馬 步 路 徑 ( 一 ) 原 先 無 解 的 矩 陣 1. 3 3 圖 48 中, 中 間 的 格 子 無 路 徑 相 連, 故 虧 格 必 須 位 於 中 間 的 格 子, 而 在 有 虧 格 後 可 得 到 一 迴 圈 2. 3 5 在 無 虧 格 之 前, 因 為 中 間 的 格 子 有 超 過 2 條 必 走 路 徑 而 無 法 完 成 所 以 在 有 虧 格 後, 必 須 讓 該 格 的 必 走 路 徑 小 於 2, 才 有 機 會 完 成 在 這 些 限 制 下 我 們 得 到 可 有 解 時 虧 格 的 位 置 必 須 在 四 個 角 落 之 一 ( 圖 49 中 灰 色 格 為 虧 格 位 置 ), 可 以 圖 49 中 相 對 於 的 位 置 做 為 起 點 與 終 點 3. 3 6 如 圖 50 51 中 所 示, 可 有 解 時 虧 格 位 置 必 須 位 於 相 對 於 灰 色 格 的 位 置, 且 起 點 與 終 點 在 的 位 置 4. 4 4 虧 格 位 於 角 落 的 格 子 時 可 使 原 無 法 相 連 的 迴 圈 相 連, 故 以 圖 52 中 為 起 點 時 可 有 解 1 6 3 4 8 7 2 5 由 上 面 的 結 果 我 們 發 現, 原 來 較 小 的 矩 陣 會 因 橋 數 限 制 而 無 法 有 解, 但 在 有 虧 格 時 也 有 可 能 找 到 一 個 以 上 的 解 圖 49 圖 50 圖 51 圖 48 圖 52-18 -
( 二 ) 在 n m 大 到 一 個 程 度 後 前 面 討 論 了 無 解 矩 陣 在 有 虧 格 時 可 以 有 解 的 情 況, 這 也 讓 我 們 好 奇 在 其 它 矩 陣 中 有 虧 格 時 可 以 有 解 的 情 況 又 是 如 何? 原 本 我 們 想 用 前 面 證 明 偶 數 格 矩 陣 有 迴 圈 和 奇 數 格 矩 陣 可 有 路 徑 的 連 接 法, 但 發 現 情 況 非 常 的 複 雜, 且 若 虧 格 可 在 矩 陣 中 任 一 位 置, 要 討 論 的 次 數 就 有 矩 陣 格 子 數 那 麼 多, 如 此 一 來 就 算 是 小 矩 陣 也 很 難 找 出 所 有 可 能, 在 大 矩 陣 就 更 是 天 方 夜 譚 了 失 敗! 不 過 後 來 我 們 想 到 不 見 得 一 定 要 用 小 的 連 成 大 的, 也 可 以 把 大 的 割 成 小 的, 而 且 發 現 用 這 種 分 割 的 方 式 只 需 找 出 一 個 小 矩 陣, 確 定 它 在 有 一 虧 格 時 可 以 有 迴 圈 或 套 色 後 格 數 多 一 格 的 顏 色 格 子 均 可 開 始, 這 樣 就 可 以 在 割 出 該 小 矩 陣 後 連 接 剩 下 的 方 格 而 證 明 出 無 限 大 時 的 情 況 但 是 過 程 中 我 們 又 遇 到 了 一 些 困 難, 這 個 小 矩 陣 似 乎 不 太 小, 它 至 少 有 一 邊 要 大 於 6, 所 以 扣 掉 對 稱 後 虧 格 位 置 至 少 有 9 種, 而 每 一 種 必 需 找 出 17 個 不 同 開 始 點 的 解, 總 共 需 要 153 個 解! 根 本 不 太 可 能 用 人 工 慢 慢 的 一 個 一 個 找, 還 好 我 們 有 電 腦 幫 忙, 找 了 好 幾 天 終 於 找 到 6 6 的 矩 陣 可 以 符 合 前 面 小 矩 陣 的 條 件 ( 以 後 稱 該 6 6 矩 陣 關 鍵 矩 陣 ), 於 是 就 用 先 分 割 後 連 接 法 來 完 成 這 一 部 分 的 證 明 成 功! 1. 分 割 與 連 接 的 方 式 將 大 的 矩 陣 用 直 線 與 橫 線 分 割 ( 每 次 隔 6 格 ) 直 到 均 超 過 中 線 ( 如 圖 53), 因 為 對 稱 的 關 係, 只 要 確 定 圖 中 黃 色 區 域 的 格 子 有 虧 格 時 的 情 況 即 可 推 至 整 個 矩 陣 又 黃 色 域 為 多 個 6 6 的 矩 陣, 所 以 只 須 確 定 虧 格 位 於 這 些 6 6 的 矩 陣 時, 可 以 有 迴 圈 或 在 套 色 後 可 以 以 與 虧 格 不 同 色 的 格 子 當 起 點, 即 可 得 到 該 大 矩 陣 不 論 虧 格 位 於 何 處 的 所 有 情 況 圖 53 而 在 用 直 線 與 橫 線 分 割 後, 要 讓 小 矩 陣 可 以 順 利 相 連 有 三 種 不 同 的 切 割 與 連 接 方 式 第 一 種 為 關 鍵 矩 陣 位 於 第 一 行, 第 二 種 為 關 鍵 矩 陣 位 於 第 一 列, 其 它 情 況 則 為 第 三 種 這 三 種 情 況 的 分 割 與 連 接 方 式 如 下 面 簡 圖 所 示 : 圖 54 圖 55 圖 55 中 藍 線 表 示 該 情 況 的 方 割 方 法, 紅 線 則 是 連 接 的 方 式 - 19 -
2. 有 虧 格 後 總 格 子 數 為 偶 數 的 矩 陣 在 奇 數 的 矩 陣 套 色 後 會 有 一 種 顏 色 的 格 子 數 較 多, 所 以 要 有 解 的 第 一 個 條 件 是 虧 格 位 置 只 能 在 套 色 後 格 數 多 一 格 的 顏 色 格 子 ( 在 圖 中 為 黃 色 的 格 子 ) 而 在 矩 陣 夠 大 時, 因 為 橋 數 多, 少 幾 條 橋 對 矩 陣 的 影 響 就 相 對 減 少, 我 們 用 上 面 介 紹 分 割 與 連 接 的 方 式 來 證 明 : 在 大 的 奇 數 矩 陣 中, 若 虧 格 位 於 套 色 後 黃 色 的 格 子, 則 可 有 迴 圈, 即 每 一 格 均 可 做 為 起 點 ( 紅 點 與 藍 點 為 各 小 矩 陣 起 點 與 終 點 的 位 置, 綠 色 箭 頭 為 連 接 方 式 ) 圖 56 圖 57-20 -
圖 58 依 著 圖 58 中 提 示 的 路 線 走, 只 要 確 定 紅 點 與 藍 點 的 位 置 可 以 做 為 起 點 與 終 點 即 可 下 面 是 6 m 時 均 可 有 解 的 證 明 圖 59 如 圖 59 中, 因 為 3 m 的 矩 陣 在 m 為 奇 數 時, 前 面 已 經 證 明 出 均 可 以 以 套 色 後 格 數 多 一 格 的 顏 色 格 子 開 始 而 結 束 在 角 落 ; 另 外 在 偶 數 時, 我 們 也 用 同 樣 的 方 法 證 出, 現 在 我 們 利 用 已 知 3 m 矩 陣 的 解, 應 用 上 圖 的 方 法 連 接 ( 為 開 始,E 為 結 束, 數 字 依 順 序 ) 即 可 得 到 6 m 的 矩 陣, 可 以 任 一 格 開 始 而 結 束 在 角 落 其 他 所 需 的 解, 我 們 也 用 同 樣 的 方 法 證 出, 但 礙 於 篇 幅 有 限 在 此 不 一 一 列 出 - 21 -
3. 有 虧 格 後 總 格 數 為 奇 數 的 矩 陣 在 奇 數 的 矩 陣 中, 因 套 色 後 兩 種 顏 色 的 格 子 數 一 樣 多, 所 以 在 大 的 矩 陣 虧 格 可 以 在 任 一 個 格 子 證 明 的 方 式 跟 前 面 奇 數 矩 陣 有 迴 圈 的 相 似, 不 過 偶 數 的 矩 陣 少 了 一 格 後 格 子 數 就 變 成 奇 數, 因 此 不 會 有 迴 圈, 所 以 不 能 像 前 面 的 證 明 繞 一 圈 即 完 成, 而 必 須 一 個 矩 陣 一 個 矩 陣 的 換, 確 定 虧 格 在 不 同 位 置 時 任 一 個 套 色 後 格 數 多 一 格 的 顏 色 格 子 均 可 完 成 圖 60 圖 中 關 鍵 矩 陣 的 任 一 紅 格 開 始 均 可 結 束 在 藍 格 而 依 箭 頭 指 示 走 紅 的 開 始 藍 的 結 束 即 可 走 完 所 有 格, 接 著 一 次 一 次 的 把 開 始 點 移 到 其 它 矩 陣, 同 樣 的 以 綠 色 箭 頭 指 示 方 向 走, 只 需 將 開 始 與 結 束 位 置 稍 微 掉 換 一 下 ( 如 下 頁 圖 61) 在 此 關 鍵 矩 陣 可 自 由 的 上 下 左 右 移 動, 所 以 當 關 鍵 矩 陣 不 是 在 第 一 行 或 第 一 列 時 均 可 得 : 虧 格 位 置 在 任 一 個 黃 格 時, 任 一 個 白 格 均 可 做 為 起 點 不 過 若 關 鍵 矩 陣 位 在 第 一 行 第 一 列, 或 虧 格 位 置 在 黃 格 時 就 需 要 用 到 圖 62 63 64 的 分 割 與 連 接 方 式 才 能 得 證 - 22 -
圖 61 圖 62-23 -
圖 63 圖 64 上 面 證 明 了 大 矩 陣 有 虧 格 的 情 況, 但 這 些 證 明 均 不 適 用 於 小 矩 陣, 因 為 小 矩 陣 無 法 再 分 割 又 如 果 想 直 接 找 出 小 矩 陣 的 所 有 可 能 又 會 因 橋 數 少, 虧 格 不 能 位 在 特 定 的 一 些 格 子, 造 成 有 太 多 的 狀 況 需 要 討 論, 所 以 目 前 還 在 研 究 如 何 證 明 小 矩 陣 的 較 佳 方 法 - 24 -
柒 結 論 一 在 n m 的 矩 陣 中 ( 限 制 n m 均 為 不 小 於 3 的 整 數 且 n 大 於 等 於 m), 至 少 有 一 馬 步 路 徑 解 的 條 件 有 : ( 一 ) n=3,m 不 等 於 3 5 6 ( 二 ) n=4,m 不 等 於 4 二 在 有 解 的 n m 矩 陣 中, 可 由 任 一 格 做 為 起 點 的 條 件 有 : ( 一 ) n m 不 為 奇 數 ( 二 ) n=3,m 不 等 於 4 8 ( 三 ) n 不 等 於 4 三 在 3 4 的 矩 陣 中 有 馬 步 路 徑 解 的 條 件 是, 下 圖 中 有 X 的 格 子 不 可 做 為 起 點, 其 餘 皆 可 四 在 3 8 的 矩 陣 中 有 馬 步 徑 路 解 的 條 件 是, 下 圖 中 有 X 的 格 子 不 可 做 為 起 點, 其 餘 皆 可 五 在 4 m 的 矩 陣 中 有 馬 步 徑 路 解 的 條 件 是, 下 圖 中 白 色 的 格 子 不 可 做 為 起 點, 其 餘 皆 可 六 在 n m 均 為 奇 數 且 n m 之 矩 陣 不 為 無 解, 則 其 有 馬 步 路 徑 解 的 必 要 條 件 是, 將 格 子 套 色 後 格 子 數 較 少 的 顏 色 格 子 不 可 做 為 起 點 七 無 解 的 矩 陣 在 有 虧 格 位 於 適 當 的 位 置 時 也 可 以 有 至 少 一 組 解 八 在 大 的 矩 陣 中 有 一 虧 格 後, 總 格 數 為 奇 數 的 矩 陣 可 以 以 套 色 後 格 數 多 一 格 的 顏 色 格 子 為 起 點, 總 格 數 為 偶 數 的 矩 陣 則 可 以 任 一 格 為 起 點 九 另 外, 在 說 明 書 及 版 面 中 未 能 呈 現 的, 有 藉 由 電 腦 程 式 的 輔 助 幫 我 們 找 出 固 定 起 始 點 之 所 有 解 及 人 工 不 易 找 出 的 解 再 者, 我 們 也 寫 出 棋 盤 上 馬 步 的 遊 戲 程 式, 可 供 初 次 接 觸 此 主 題 的 人 玩, 引 導 他 們 一 窺 馬 步 的 奧 秘, 在 我 們 現 場 的 電 腦 中 有 展 示 出 來 可 供 大 家 參 考 十 希 望 未 來 能 夠 透 過 將 棋 盤 座 標 化, 找 出 最 短 路 徑 的 函 數 模 式, 為 做 IC 設 計 與 快 遞 或 宅 急 便 之 運 輸 路 線 規 劃 之 利 用 - 25 -
捌 參 考 資 料 一 林 克 瀛 ( 民 93) 騎 士 漫 遊 方 陣 與 魔 方 陣 數 學 傳 播 28 卷 3 期,64-68 二 林 克 瀛 ( 民 93) 六 階 棋 盤 上 的 騎 士 循 環 漫 遊 共 有 1245 種 數 學 傳 播 28 卷 4 期,63-69 三 林 建 宏 ( 民 75) 5 階 棋 盤 之 騎 士 漫 遊 僅 有 112 個 解 數 學 傳 播 10 卷 2 期,20-27 四 胡 咸 編 ( 民 87) 離 散 數 學 台 北 市 : 茂 昌 五 徐 力 行 ( 民 92) 沒 有 數 字 的 數 學 台 北 市 : 天 下 六 張 遠 南 ( 民 86) 使 人 聰 明 的 智 力 遊 戲 台 北 市 : 九 章 七 單 墫 ( 民 83) 趣 味 的 圖 論 問 題 新 竹 市 : 凡 異 八 趙 文 敏 ( 民 82) 寓 數 學 於 遊 戲 ( 第 一 輯 ) 台 北 市 : 九 章 九 有 趣 的 數 學 旅 行 台 北 市 : 親 代 叢 書 編 十 科 學 教 授 ( 數 學 ) 台 北 市 : 牛 頓 出 版 社 編 十 一 http//:www.math.sinica.edu.tw/media/default.jsp - 26 -
中 華 民 國 第 四 十 五 屆 中 小 學 科 學 展 覽 會 評 語 高 中 組 數 學 科 040420 棋 盤 上 的 馬 步 臺 北 市 立 麗 山 高 級 中 學 評 語 : 1. 馬 步 問 題 頗 為 常 見, 研 究 問 題 不 妨 參 考 西 方 數 學 家 的 想 法 2. 透 過 數 學 軟 體 的 強 力 計 算, 尋 找 可 能 分 類 的 方 式, 以 了 解 其 對 稱 性 及 結 構