壹、研究動機

類別 : 數學類 篇名 : 棋子跳躍之遊戲研究 作者 : 蔡易霖 台南市私立南光高中 高二忠班 翁煜傑 台南市私立南光高中 高二忠班 吳泳昇 台南市私立南光高中 高二忠班 指導老師 : 黃韻如老師

壹 前言 一 研究動機 課餘時間, 我們幾個同學常聚在一起玩各種益智遊戲 有一天, 我們接觸一 個類似跳棋的小遊戲, 稱為 移位跳棋 用一個例子說明 移位跳棋 規則將三顆白棋放置在 1 3 的位置, 同時將三顆黑棋放在 5 6 7 的位置 如下 : 7 圖一 目的 : 將黑 白棋的位置互換, 即可完成 移動規則 :a. 永遠保持每個格子最多一顆棋子 b. 任意一棋子可 移至相鄰空格 或 跳過相鄰棋子置入空格內 上述例子是黑 白棋各三顆的移位跳棋遊戲, 容易解決並求得最佳移動方式 若 將其將此遊戲推廣至 m 個黑棋與 n 個白棋就沒這麼容易 所以, 為求得最佳移 動方式 ( 最少移動步數 ), 我們展開研究並試圖求得一般解 二 研究目的 ( 一 ) N-N 型移位跳棋 的最佳移動方式與最少移動步數探討 ( 二 ) M-N 型移位跳棋 的最佳移動方式與最少移動步數探討 貳 正文 一 研究過程 ( 一 ) 研究一 N-N 型移位跳棋 遊戲的探討 何謂 N-N 型移位跳棋? 表有 n+1 的格子, 初始狀態為 n 顆白棋放置在 1 n 的位置, n 顆黑棋放置在 n+ n+3 n+1 的位置 1

以下用幾個小例子, 試圖推廣至一般的 N-N 型移位跳棋 - 型移位跳棋 移動前的棋盤圖 : 移動過程 : 圖二 總計 8 步 1 每次只能移動一顆棋子 每一顆被移動的棋子可以選擇下列兩種移動方式 (1) 移至相鄰空格 () 跳過相鄰棋子置入空格內 3 記錄完成步數

記錄步數 : 表一 操作次別各邊移動棋子步數 一 二 三 四 五 最少步數 1 3 3 3 3 3 3 10 10 8 8 8 8 3 17 17 15 15 15 15 4 30 30 6 4 4 4 5 39 37 35 35 35 35 6 5 48 48 48 48 48 發現 : 從操作過程中發現 N-N 型移位跳棋, 要走最少步數有幾種現象 : 1 白 黑棋子都呈現只能前進沒有後退的情形 在跳棋的過程中, 會有雙色一對一交錯的圖形 3 先移動的顏色會較晚到達指定位置 4 若仔細去觀察移動方式, 會發現移動的顏色具有一定對稱性 以下所舉的例子皆以先移動白色為示範 : n=1 1 3 ( 圖三 -1) 移動顏色 : 白 黑 白 n= ( 圖三 -) 移動顏色 : 白 黑 黑 白 白 黑 黑 白 n=3 7 ( 圖三 -3) 移動顏色 : 白 黑 黑 白 白 白 黑 黑 黑 白 白 白 黑 黑 白 n=4 7 8 9 ( 圖三 -4) 移動顏色 : 白 黑 黑 白 白 白 黑 黑 黑 黑 白 白 白 白 黑 黑 黑 黑 白 白 白 黑 黑 白 3

由上面觀察, 我們發現棋子移動時的顏色變化似乎是具有規律性 因此, 歸納以下特性 : 1 棋子移動時所變換的顏色是具有對稱性的, 若首先移動白色棋子, 則最後一 個移動的必為白色 連色移動, 即同一種顏色連續移動之現象, 其連色的最大值等於各邊所含的 棋子數, 如 : 在 n=3 的情況中, 中間連色的最大值為 3( 也就是黑 黑 黑 ) 3 連色最大值的數量皆等於 3( 此處不考慮顏色 ) 如 :n=4 的情況中, 中間連 色最大值的數量為 3( 也就是黑 黑 黑 黑 白 白 白 白 黑 黑 黑 黑 ) 4 移動顏色是以規律性遞增後再遞減 (1 3 a 1 1 n a n a 1 n a n 1 3 1), 而移動完 A 色之後, 下次移動就要換成 B 色, 假設起始的顏色是 白 為 n=3 之情形 : (1) 移動 1 次 白, 連色數 : 以 1 為起始 白 () 移動 1 次 黑黑, 連色數 :1+1= 黑黑 (3) 移動 1 次 白白白, 連色數 :+1=3 白白白 此時已為最大值了, 所以 連色數為 4 的要寫 3 次 白白白 黑黑黑 白白白 (4) 移動 1 次 黑黑, 連色數 3-1= 黑黑 此時已經過了最大值, 所以要開始遞減了 (5) 移動 1 次 白, 連色數 -1=1 白 總移動情形 : 白 黑 黑 白 白 白 黑 黑 黑 白 白 白 黑 黑 白 總步數為 :1++3+3+3++1=15, 符合實際移動結果 因此我們可以輕易推出, 當 n=4 時, 移動顏色之情形應為 : 白 黑 黑 白 白 白 黑 黑 黑 黑 白 白 白 白 黑 黑 黑 黑 白 白 白 黑 黑 白總步數為 :1++3+4+4+4+3++1=4, 符合實際移動結果 尋找規則 令 A (n) 為 N-N 型移位跳棋 移動最少步數 可以利用上面移動顏色之規律性來推導出最少步數, 則其公式推導為 : A ( n) 1 3 ( n 1) n n n ( n 1) 3 1 (1 3 ) n ( n 1) n ( n ) 再以 表一 中數據驗證, 亦可皆有符合此公式 4

( 二 ) 研究二 M-N 型移位跳棋 遊戲的探討 何謂 M-N 型移位跳棋? 表有 m+n+1 的格子, 初始狀態為 m 顆白棋放置在 1 m 的位置, n 顆黑棋放置在 m+ m+3 m+n+1 的位置 本文只討論當 m=n+1 的 M-N 型移位跳棋 3- 型移位跳棋 移動前的棋盤圖 : 移動過程 : 5

圖四 總計 11 步 1 每次只能移動一顆棋子 每一顆被移動的棋子可以選擇下列兩種移動方式 (1) 移至相鄰空格 () 跳過相鄰棋子置入空格內 3 記錄完成步數 記錄步數 : 表二 操作次別各邊移動棋子步數 一 二 三 四 五 最少步數 (,1) 7 7 5 5 5 5 (3,) 11 13 11 11 11 11 (4,3) 19 19 19 19 19 19 (5,4) 31 9 31 9 9 9 (6,5) 41 41 41 41 41 41 發現 : 從操作過程中發現 M-N 型移位跳棋, 要走最少步數有幾種現象 : 1 白 黑棋子都呈現只能前進沒有後退的情形 在跳棋的過程中, 會有雙色一對一交錯的圖形 3 先移動的顏色會較早到達指定位置 4 顏色移動情形和原先 N-N 型移位跳棋 是相似的, 但略微減少一些移動 ( 三 ) 為了解釋顏色移動是有相似的, 我們要用 對照的方法 來解釋 N-N 型移 位跳棋 和 M-N 型移位跳棋 的關係 6

1 M-N 型移位跳棋 (,1)& N-N 型移位跳棋 (,) (,1) 1 3 4 ( 圖五 -1) 移動顏色 : 白 黑 白 白 黑 (,) ( 圖五 -) 移動顏色 : 白 黑 黑 白 白 黑 黑 白 M-N 型移位跳棋 (3,) & N-N 型移位跳棋 (3,3) (3,) ( 圖六 -1) 移動顏色 : 白 黑 黑 白 白 白 黑 黑 白 白 黑 (3,3) 7 ( 圖六 -) 移動顏色 : 白 黑 黑 白 白 白 黑 黑 黑 白 白 白 黑 黑 白 註 : 框起來的顏色即表示 M-N 型移位跳棋 中沒有的 由上面觀察, 我們發現幾個特性 : (1) N-N 型移位跳棋 的尾端去掉 黑 白 即為 非直線等長型 之尾端 () 在 N-N 型移位跳棋 的中間段所需去除的步數似乎不具有明顯的規律 我們曾經試圖建立這兩者的關係, 但目前尚未成功 (3) 由 M-N 型移位跳棋 和 N-N 型移位跳棋 步數的比較關係可得下表 : 表三 類型直線等長型非直線等長型相差步數 最少步數 (,)8 (,1)5 3 (3,3)15 (3,)11 4 (4,4)4 (4,3)19 5 (5,5)35 (5,4)9 6 (6,6)48 (6,5)41 7 因此我們可以推得當 M-N 型移位跳棋 為 (n+1,n) 其與 N-N 型移位跳棋 (n+1,n+1) 的相差步數為 :n+ 7

令 B (n) 為 M-N 型移位跳棋 最少步數 ( m=n+1 ), 則公式推導即為 : B (n) 直線等長型最少步數 - 相差步數 A ( n 1) ( n ) ( n 1)[( n 1) ] ( n ) ( n 1)( n 3) ( n ) 4n 3 ( n ) 3n 1 再以 表二 數據驗證, 亦皆有符合此公式 ( 四 ) 討論 : 試圖以直接觀察而非以比較的方式來探討 M-N 型移位跳棋 (m,n) 以 m 表示白棋數量 n 表示黑棋數量 (,1): 移動顏色 : 白 黑 白 白 黑 (3,): 移動顏色 : 白 黑 黑 白 白 白 黑 黑 白 白 黑 (4,3): 移動顏色 : 白 黑 黑 白 白 白 黑 黑 黑 白 白 白 白 黑 黑 黑 白 白 黑 (5,4): 移動顏色 : 白 黑 黑 白 白 白 黑 黑 黑 黑 白 白 白 白 白 黑 黑 黑 黑 白 白 白 白 黑 黑 黑 白 白 黑寫作算數式 ( 紅色表示為白棋移動, 黑色為黑棋移動 ) (,1) 1+1++1 (3,) 1++3+++1 (4,3) 1++3+3+4+3++1 (5,4) 1++3+4+5+4+4+3++1 明顯可看出移動過程中, 同色棋連續最多步數等於 m, 且為白棋, 而黑棋的最多連續步數則為 n, 這是由於移動過程中不可後退的性質所致 以下為從頭開始移動到完成步數為 m 的步驟後之情況 : (,1) 1 3 4 ( 圖七 -1) (3,) ( 圖七 -) (4,3) 7 8 ( 圖七 -3) 8

(5,4) 7 8 9 10 ( 圖七 -4) 在進行完步數為 m 的步驟後, 可見 m 為奇數偶數時有明顯差異 : 1. 若 m 為偶數, 則有兩顆白棋抵達右邊, 且其餘呈黑白棋交錯分布. 若 m 為奇數, 則有一顆白棋抵達右邊, 且其餘呈黑白棋交錯分布 可將移動過程分為兩種討論 : 1 若 m 為偶數, 則在步數為 m 之前的兩個步驟, 步數皆等於 n 在此情形下, 若將 m 的前一項 n 加上 1, 則此項變成 m 可看出其規律性 B(n) ( 1 3 m ) m ( m 1) 3 1 1 ( 1 3 m) 1 m( m 1) 1 m ( m 1) 1 若 m 為偶數, 則在步數為 m 之後的兩個步驟, 步數皆等於 n 將 m 的後一項 n 加上 1, 則此項變成 m 可得總步數亦為 m ( m 1) 1 但此式僅適用於 m n 1的情況 參 結論 一 透過研究歸納和整理, 可得以下幾項公式 : ( 一 ) N-N 型移位跳棋 表有 n+1 的格子, 初始狀態為 n 顆白棋放置在 1 n 的位置, n 顆白棋放置在 n+ n+3 n+1 的位置 令 A (n) 為 N-N 型移位跳棋 移動最少步數, 則 A ( n) 1 3 ( n 1) n n n ( n 1) 3 1 (1 3 n) n n ( n 1) n n n n ( n ) 9

( 二 ) M-N 型移位跳棋 表有 m+n+1 的格子, 初始狀態為 m 顆白棋放置在 1 m 的位置, n 顆白棋放置在 m+ m+3 m+n+1 的位置 令 B (n) 為 M-N 型移位跳棋 最少步數 ( m=n+1 ), 則 證法一 : 將 M-N 型移位跳棋與 N-N 型移位跳棋直接做比較 B (n) 直線等長型最少步數 - 相差步數 A ( n 1) ( n ) ( n 1)[( n 1) ] ( n ) ( n 1)( n 3) ( n ) 4n 3 ( n ) 3n 1 證法二 : 以直接觀察之方式來求最少步數 B(n) ( 1 3 m ) m ( m 1) 3 1 1 ( 1 3 m) 1 m( m 1) 1 m ( m 1) 1 又 m n 1代入此式 m( m 1) 1 n 3n 1 可發現與上式等值 二 心得與未來的發展 : 雖然在找尋上述規律的過程中, 遭遇挫折常令我們感到無助, 但在大家齊心討論摸索中, 最終看清楚該遊戲的最佳移動方式規律並完全解決當初設定的問題 這過程真得讓我們學到許多東西, 引起想探索更有趣的數學題材 光是跳棋遊戲就有許多變化型可以研究, 例如 : 將棋子的顏色擴充 改變棋子移動規則或者是二維互換的序列拓展 等 這些變形的遊戲將使難度更加提高, 但也更能增加遊戲的趣味性與不確定度 肆 引註資料 一 高中組二件科學展覽優勝作品 為針對直線型且空格不固定的方式進行解題一為 < 走走跳跳 > 另一為 < 乾坤大挪移 > 二 凡異出版社 < 數學遊戲 > 一書提及直線型移位遊戲三 故鄉出版社 < 益智遊戲 > 一書中提及直線型移位遊戲四 九章出版社 < 使人聰明的智力遊戲 > 一書中則提到等長直線型的移位遊戲, 並附上完成所需的最小步數解答 10