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

Size: px

Start display at page:

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

仰豫屈
5 years ago
Views:

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

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

3 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

4 第 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 完成先列完黑白各一粒到黑白各四粒, 接下來就要觀察過程 ( 五 ) 由 ( 一 )( 二 )( 三 )( 四 ) 觀察, 可列出表 ( 一 ) 中之總平移次數總跳躍次數最少移動次數, 接著推出公式, 並預測每邊棋子為五粒時的總平移次數總跳躍次數與最少移動次數表 ( 一 ) 每邊棋子數總平移次數總跳躍次數最少移動次數設每邊有 N 粒棋, 則每粒棋移動格數為 (N + 1) 步, 故總移動格數為 N (N + 1) = N + N 設每邊有 N 粒棋, 則由表 ( 一 ) 觀察得知總跳躍次數為每邊棋子數的平方, 而其原因為, 每粒白棋都必須跳過黑棋或被黑棋跳過, 共需跳躍 N 次, 故總跳躍次數為 N 3 設每邊有 N 粒棋, 則由表 ( 一 ) 知總平移次數為每邊棋子數的兩倍, 其原因為, 由 1 知, 總移動格數為 N + N, 而總跳躍次數為 N, 跳躍一次等於移動兩格, 故總移動次數減總跳躍次數的兩倍會等於總平移次數, 即 (N + N) N = N 4 因為總移動次數 = 總平移次數 + 總跳躍次數, 由 3 之結果, 即可得 4

5 最少移動次數為 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

6 第 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

7 第 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) () 觀察, 可列出表 ( 二 ) 中之全部黑棋或白棋一起平移一格的步數與最少移動次數, 接著推出公式, 並預測五粒棋全部一起平移一格的步數, 與當中間空兩格每邊棋子為五粒時位置交換的最少移動次數表 ( 二 ) 每邊棋子數全部黑棋或白棋一起平移一格的步數最少移動次數

8 (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:

9 由推廣 ( 一 ) 知, 全部黑棋或白棋一起平移一格需 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) 數學思考台北市: 九章出版社. 生成函數方法解一般遞迴數列 3. spaces.isu.edu.tw/upload/19585/dm/ch06.pdf 遞迴關係與演算法分析 9

?C???????????l?????????s

?C???????????l?????????s 青蛙跳 - 黑白棋互換之探究摘要本研究主要是探討黑白棋在同一直線的兩側, 中央空置一格, 每個棋子可藉由移動一格或跳過相鄰一個棋子而前進, 黑白棋互換的最佳走法和移動總步數利用將黑白棋互換的每一個步驟表列出來, 從中獲得其規則為黑白相間, 數量遞加至 n, 而每邊各 n 個的移動總步數為 n (n+2); 每邊各 n 個和 n-1 個 ( 相差一個 ) 的移動總步數為 n²+n-1 壹研究動機