壹 前言 有一次, 我們在學校的圖書館看有關於數學的書, 我們看的不是有著複雜計算的數學, 而是需要動動腦 動手做做看的數學, 翻著翻著我們翻到了一篇有關於棋子的題目, 剛好我們都很喜歡下棋, 所以都對這道題目特別感興趣, 我們便決定要把這題解出來 我們開始思考如何移動棋子, 我們從少的開始算起,

投稿類別 : 數學類 篇名 : 黑白跳棋遊戲 作者 : 姜文闕 國立鳳山高中 高二 14 班王睿紳 國立鳳山高中 高二 14 班陳永紳 國立鳳山高中 高二 14 班 指導老師 : 許純瑋老師 鍾永鴻老師 1

壹 前言 有一次, 我們在學校的圖書館看有關於數學的書, 我們看的不是有著複雜計算的數學, 而是需要動動腦 動手做做看的數學, 翻著翻著我們翻到了一篇有關於棋子的題目, 剛好我們都很喜歡下棋, 所以都對這道題目特別感興趣, 我們便決定要把這題解出來 我們開始思考如何移動棋子, 我們從少的開始算起, 因為我們知道如果沒有找到規律, 數字太大計算時會很亂, 而且也容易算錯, 不久我們找到通式, 題目便快速得解出來了 雖然最後我們都知道這題的答案了, 但是我們還是對這類的題目很有興趣, 便開始假設一些條件然後去思考其中的關聯性, 進而解出通式, 但過程中我們開始懷疑這樣真的就對了嗎? 這樣的觀點使我們在過程中有所困擾, 所以我們想藉此慢慢研究其中的奧妙 貳 正文 一 介紹 十一個空位排成一直線, 將五粒黑子與五粒白子放入, 五粒黑子放在一側的五個位子上, 五粒白子放在另一側的五個位子上, 正中央不要放棋子, 如圖 ( 一 ), 現在想把黑棋與白棋位置交換, 但只能將棋子平移到相鄰的空位或跳過一粒棋子到另一個位置 則最少要動幾次棋? ( 以下黑子由 B 表示, 白子由 W 表示 ) 二 過程 圖 ( 一 ) 以上介紹的是五粒黑子與五粒白子的情形, 因為黑白各有五粒棋, 棋數 較多, 一次討論太過於複雜, 故我們由黑白各一粒 二粒 三粒 四粒棋開 始列出交換的過程 ( 一 ) 黑白棋各一粒時 : B W 第 1 步 BW 第 步 WB 第 3 步 W B 完成 ( 二 ) 黑白棋各二粒時 :

BB WW 第 1 步 B BWW 第 步 BWB W 第 3 步 BWBW 第 4 步 BW WB 第 5 步 WBWB 第 6 步 W BWB 第 7 步 WWB B 第 8 步 WW BB 完成 ( 三 ) 黑白棋各三粒時 : BBB WWW 第 1 步 BB BWWW 第 步 BBWB WW 第 3 步 BBWBW W 第 4 步 BBW WBW 第 5 步 B WBWBW 第 6 步 BWBWBW 第 7 步 WB BWBW 第 8 步 WBWB BW 第 9 步 WBWBWB 第 10 步 WBWBW B 第 11 步 WBW WBB 第 1 步 W WBWBB 第 13 步 WW BWBB 第 14 步 WWWB BB 第 15 步 WWW BBB 完成 ( 四 ) 黑白棋各四粒時 : BBBB WWWW 第 1 步 BBB BWWWW 第 步 BBBWB WWW 第 3 步 BBBWBW WW 第 4 步 BBBW WBWW 第 5 步 BB WBWBWW 第 6 步 B BWBWBWW 第 7 步 BWB BWBWW 第 8 步 BWBWB BWW 3

第 9 步 BWBWBWB W 第 10 步 BWBWBWBW 第 11 步 BWBWBW WB 第 1 步 BWBW WBWB 第 13 步 BW WBWBWB 第 14 步 WBWBWBWB 第 15 步 W BWBWBWB 第 16 步 WWB BWBWB 第 17 步 WWBWB BWB 第 18 步 WWBWBWB B 第 19 步 WWBWBW BB 第 0 步 WWBW WBBB 第 1 步 WW WBWBBB 第 步 WWW BWBBB 第 3 步 WWWWB BBB 第 4 步 WWWW BBBB 完成 先列完黑白各一粒到黑白各四粒, 接下來就要觀察過程 ( 五 ) 由 ( 一 )( 二 )( 三 )( 四 ) 觀察, 可列出表 ( 一 ) 中之總平移次數 總跳躍次數 最少移動次數, 接著推出公式, 並預測每邊棋子為五粒時的總平移次數 總跳躍次數與最少移動次數 表 ( 一 ) 每邊棋子數 1 3 4 5 總平移次數 4 6 8 10 總跳躍次數 1 4 9 16 5 最少移動次數 3 8 15 4 35 1 設每邊有 N 粒棋, 則每粒棋移動格數為 (N + 1) 步, 故總移動格數為 N (N + 1) = N + N 設每邊有 N 粒棋, 則由表 ( 一 ) 觀察得知總跳躍次數為每邊棋子數的平方, 而其原因為, 每粒白棋都必須跳過黑棋或被黑棋跳過, 共需跳躍 N 次, 故總跳躍次數為 N 3 設每邊有 N 粒棋, 則由表 ( 一 ) 知總平移次數為每邊棋子數的兩倍, 其原因為, 由 1 知, 總移動格數為 N + N, 而總跳躍次數為 N, 跳躍一次等於移動兩格, 故總移動次數減總跳躍次數的兩倍會等於總平移次數, 即 (N + N) N = N 4 因為總移動次數 = 總平移次數 + 總跳躍次數, 由 3 之結果, 即可得 4

最少移動次數為 N + N 三 推廣 ( 一 ) 中間空格數為 時 : 十二個空位排成一直線, 將五粒黑子與五粒白子放入, 五粒黑子放在一側的五個位子上, 五粒白子放在另一側的五個位子上, 正中央兩個位置不要放棋子 如圖 ( 二 ) 現在想把黑棋與白棋的位置交換, 但只能將棋子平移到相鄰的空位或跳過一粒棋子到另一個位置 則最少要動幾次棋? ( 以下黑子由 B 表示, 白子由 W 表示 ) 圖 ( 二 ) 剛開始, 我們也想和之前一樣直接列出所有交換的過程, 再來觀察, 但是後來我們發現, 如果將所有黑棋全部向右平移一格, 整題就和上一題一模一樣了, 交換完成後, 再將白棋全部向左平移一格, 即可完成 所以我們必須先推出每邊 N 粒棋子時, 全部一起平移一格的最少步數, 推出公式以後, 只需要將它與上一題結論公式合併, 便可以得到這題的公式 我們在算全部白棋或黑棋一起平移一格的最少步數時, 發現若把奇數 偶數分開來算, 計算過程更簡單, 也可以算得比較快, 故以下我們將奇數 偶數分開討論 1 每邊有奇數個棋子時, 令 N = k 1 (1) 黑白棋各一粒時 : B W 第 1 步 B W 第 步 BW 第 3 步 WB 第 4 步 W B 第 5 步 W B 完成 () 黑白棋各三粒時 : BBB WWW 第 1 步 B BB WWW 第 步 BBB WWW 5

第 3 步 BB BWWW 第 4 步 BBWB WW 第 5 步 BBWBW W 第 6 步 BBW WBW 第 7 步 B WBWBW 第 8 步 BWBWBW 第 9 步 WB BWBW 第 10 步 WBWB BW 第 11 步 WBWBWB 第 1 步 WBWBW B 第 13 步 WBW WBB 第 14 步 W WBWBB 第 15 步 WW BWBB 第 16 步 WWWB BB 第 17 步 WWW BBB 第 18 步 WW W BBB 第 19 步 WWW BBB 完成 每邊有偶數個棋子時, 令 N = k (1) 黑白棋各二粒時 : BB WW 第 1 步 BB WW 第 步 B BWW 第 3 步 BWB W 第 4 步 BWBW 第 5 步 BW WB 第 6 步 WBWB 第 7 步 W BWB 第 8 步 WWB B 第 9 步 WW BB 第 10 步 WW BB 完成 () 黑白棋各四粒時 : BBBB WWWW 第 1 步 BB BB WWWW 第 步 BBBB WWWW 6

第 3 步 BBB BWWWW 第 4 步 BBBWB WWW 第 5 步 BBBWBW WW 第 6 步 BBBW WBWW 第 7 步 BB WBWBWW 第 8 步 B BWBWBWW 第 9 步 BWB BWBWW 第 10 步 BWBWB BWW 第 11 步 BWBWBWB W 第 1 步 BWBWBWBW 第 13 步 BWBWBW WB 第 14 步 BWBW WBWB 第 15 步 BW WBWBWB 第 16 步 WBWBWBWB 第 17 步 W BWBWBWB 第 18 步 WWB BWBWB 第 19 步 WWBWB BWB 第 0 步 WWBWBWB B 第 1 步 WWBWBW BB 第 步 WWBW WBBB 第 3 步 WW WBWBBB 第 4 步 WWW BWBBB 第 5 步 WWWWB BBB 第 6 步 WWWW BBBB 第 7 步 WW WW BBBB 第 8 步 WWWW BBBB 完成 3 由(1) () 觀察, 可列出表 ( 二 ) 中之全部黑棋或白棋一起平移一格的步數與最少移動次數, 接著推出公式, 並預測五粒棋全部一起平移一格的步數, 與當中間空兩格 每邊棋子為五粒時位置交換的最少移動次數 表 ( 二 ) 每邊棋子數 1 3 4 5 全部黑棋或白棋一 1 1 3 起平移一格的步數 最少移動次數 5 10 19 8 41 7

(1) 故當每邊棋子數為 k 1 與 k 時, 全部一起平移一格的步數會相 同, 即兩邊棋子數每各加二, 全部黑棋或白棋一起平移一格的步 數便會多一 設每邊有 N 粒棋, 且 N 為奇數, 令 N = k 1 由 表 ( 二 ) 可推得, 全部一起平移一格的步數為 N+1 步 而當 N 為偶 數, 令 N = k, 由表 ( 二 ) 可推得全部一起平移一格的步數為 N 步 又由二知當中間空格只有一格時, 最少移動次數為 N + N 且 黑棋全部一起向右平移一格的步數等於白棋全部一起向左平移 一格的步數 所以每邊的棋子為奇數個, 且中間有兩個空格時, N+1 其最少移動次數為 + N + N = N + 3N + 1; 若每邊的 棋子為偶數個, 且中間有兩個空格時, 其最少移動次數為 N + N + N = N + 3N ( 二 ) 中間空格數為 M 時 : 而 (N+M) 個空位排成一直線, 將 N 粒黑子與 N 粒白子放入,N 粒黑子放在一側的 N 個位子上,N 粒白子放在另一側的 N 個位子上, 正中央 M 個位置不要放棋子, 如圖 ( 三 ), 現在想把黑棋與白棋的位置交換, 但只能將棋子平移到相鄰的空位或跳過一粒棋子到另一個位置 則最少要動幾次棋? N 個黑子 M 個空位 ( 圖三 ) 題目 我們一樣先將 N 分為奇數與偶數討論 N 個白子 1 當每邊有奇數個棋子時, 令 N = k 1: 由推廣 ( 一 ) 知, 全部黑棋或白棋一起平移一格需 8 N+1 步, 現在中間空 格數為 M, 則黑棋一開始必須全部一起向右平移 (M-1) 格, 而最後白 棋也必須全部一起向左平移 (M-1) 格 故當邊有奇數個棋子, 且中間 空格數為 M 時, 其最少移動步數為 (N + N) + (M 1) N + 1 = N + MN + M + N 1 每邊有偶數個棋子時, 令 N = k:

由推廣 ( 一 ) 知, 全部黑棋或白棋一起平移一格需 N 步, 由 1 之討論, 故可得當每邊有偶數個棋子, 且中間空格數為 M 時, 其最少移動步數為 (N + N) + (M 1) N = N + MN + N 參 結論 一 當每邊有 N 粒棋, 且中間空格數為 1 時, 總跳躍次數為 N, 總平移次數為 N 故最少移動次數為 N + N 二 當每邊有 N 粒棋, 且中間空格數為 時 : ( 一 ) 若每邊的棋子為奇數個, 則其最少移動次數為 N + 3N + 1 ( 二 ) 若每邊的棋子為偶數個, 則其最少移動次數為 N + 3N 三 當中間空格數為 M 時 : ( 一 ) 若每邊的棋子為奇數個, 則其最少移動次數為 N + MN + M + N 1 ( 二 ) 若每邊的棋子為偶數個, 則其最少移動次數為 N + MN + N 肆 引註資料 1. 建國高中 49 屆 314 班全體同學 ( 譯 )(011) 數學思考 台北市: 九章出版社. www.math.ntu.edu.tw/~msa/act/mathcamp/95page/lecture/i.doc 生成函數方法解一般遞迴數列 3. spaces.isu.edu.tw/upload/19585/dm/ch06.pdf 遞迴關係與演算法分析 9