(Microsoft Word - 02\274\306-\300u\277\357-A004\260\256\251[\244j\256\277\262\276.doc)

Size: px

Start display at page:

Download "(Microsoft Word - 02\274\306-\300u\277\357-A004\260\256\251[\244j\256\277\262\276.doc)"

稳豫唐
5 years ago
Views:

1 高雄市 96 年度國小學生獨立研究成果發表競賽作品說明書類別 : 數學類作品名稱 : 乾坤大挪移 - 最少步數之探討學校 : 愛國國小研究者 : 蔡惟名王冠承陳淇鈺廖宜威謝富丞陳柏勳指導老師 : 曹秀美張家慶 ~1~

2 乾坤大挪移 ~ 最少步數之探討摘要下課時, 我們常在教室後面的益智區玩跳棋, 要將棋子以最快的速度, 也就是最少的步數移到對面才能贏對方, 不服輸的我們, 常常為了要贏棋而絞盡腦汁所以就想要研究同一條直線下, 如何以最少的步數, 把二個不同顏色的棋子對調結果發現 : 一左邊有 X 個白色棋子, 右邊亦有 X 個黑色棋子, 中間有 1 個空格不同顏色的棋子可以跳躍過去, 同顏色的棋子不可以跳躍在此條件下, 要把不同顏色交換過來, 需要 X 2 +2X 步二左邊有 X 個白色棋子, 右邊亦有 X 個黑色棋子, 中間有 Y 個空格在上述規則限制下, 要把不同顏色交換過來, 最少需要 X 2 +2XY 步三左邊有 X 個白色棋子, 右邊有 Y 個黑色棋子, 中間有 1 個空格在上述規則限制下, 要把不同顏色交換過來, 最少需要 XY+X+Y 步四左邊有 X 個白色棋子, 右邊有 Y 個黑色棋子, 中間有 Z 個空格在上述規則限制下, 要把不同顏色交換過來, 最少需要 XY+YZ+ZX 步 ~2~

3 乾坤大挪移 ~ 最少步數之探討壹研究研究動機下課時, 我們常在教室後面的益智區玩跳棋, 要將棋子以最快的速度, 也就是最少的步數移到對面才能贏對方, 不服輸的我們, 常常為了要贏棋而絞盡腦汁所以就想要研究同一條直線下, 如何以最少的步數, 把二個不同顏色的棋子對調, 於是請老師帶領我們做這個研究貳研究目的一左邊有 X 個白色棋子, 右邊亦有 X 個黑色棋子, 中間有一個空格不同顏色的棋子可以跳躍過去, 同顏色的棋子不可以跳躍在此限制條件下, 想要把不同顏色交換過來, 最少需要幾步? 二左邊有 X 個白色棋子, 右邊亦有 X 個黑色棋子, 中間有 Y 個空格在上述規則限制下, 想要把不同顏色交換過來, 最少需要幾步? 三左邊有 X 個白色棋子, 右邊有 Y 個黑色棋子, 中間有 1 個空格在上述規則限制下, 要把不同顏色交換過來, 最少需要幾步? 四左邊有 X 個白色棋子, 右邊有 Y 個黑色棋子, 中間有 Z 個空格在上述規則限制下, 想要把不同顏色交換過來, 最少需要幾步? 參研究研究內容一方法 : 比較簡單的情形, 我們以演繹法直接推演而較複雜的情形, 則以歸納法來求之所謂歸納法是將現有東西的規律, 歸納成一種結論或公式二內容 : 移動規則是一次只能動一步, 遇到不同顏色的棋子可以跳躍過去兩邊不同顏色的棋子要完全互相交換時, 求最少的步數為了研究方便, 先假設 : ( 一 ) 先固定中間空格空格數為 1, 且設二邊設二邊棋數個數個數相同, 均為 X 為方便推論起見, 移動方式都暫規定先移動左邊的白棋在此先將 X = 1, X = 2, X = 3 的情形都表列出來 : X = 1 X = 2 X = 3 步數 _ 步數 _ 步數 _ ~3~

4 1 1 _ 1 _ 2 2 _ 2 _ 3 3 _ 3 _ 4 _ 4 _ 5 _ 5 _ 6 _ 6 _ 7 _ 7 _ 8 _ 8 _ 9 _ 10 _ 11 _ 12 _ 13 _ 14 _ 15 _ 我們發現到在移動的過程中, 一定有一個步驟會到達空格在最左邊及一個步驟到達空格在最右邊, 為了方便起見, 我們假設在黑白各 X 個棋子的情況下 : S X : 表起始狀態 L X : 表空格在最左邊的狀態 ;N(L X ) 表從起始狀態到 L X 狀態所需的步數 R X : 表空格在最右邊的狀態 ;N(R X ) 表從起始狀態到 R X 狀態所需的步數 E X : 表結束完成後的狀態,N(E X ) 兩顏色的棋子完全對調過來時所需的步數另外我們再用 N(LR X ) 表從 L X 狀態到 R X 狀態的步數 N(RL X ) 表從 R X 狀態到 L X 狀態的步數當 X = 1 時的經過情形是 S 1 L 1 R 1 E 1 當 X = 2 時的經過情形是 S 2 R 2 L 2 E 2 當 X = 3 時的經過情形是 S 3 L 3 R 3 E 3 我們再將三種情形時每個狀態之間變動的步數列表如下 : S L( 或 S R ) L R( 或 R L ) R E( 或 L E ) X = 1 N(L 1 ) = 1 N(LR 1 ) = 1 N(R 1 ) = 1 X = 2 N(R 2 ) = 3 N(RL 2 ) = 2 N(L 2 ) = 3 X = 3 N(L 3 ) = 6 N(LR 3 ) = 3 N(R 3 ) = 6 ~4~

5 我們發現到 N(L X ) 必等於 N(R X ) 亦即 S X L X 與 R X E X 的步驟數必定是一樣的, 這是因為棋子移動的過程是成對稱的, 即 : 從最起始狀態到空格在最左邊的步驟數 = 空格在最右邊到達完成的步驟數又從空格在最左邊變成空格在最右邊 ( 即 L X R X ), 或從空格在最右邊變成空格在最左邊 ( 即 R X L X ) 的步驟數剛好就等於 X ( 即黑棋或白棋的個數 ) 這是很顯然的, 因為一邊有 X 個棋子, 剛好需要跳 X 步才能把空格從最左邊換成到最右邊亦即 :N(LR X )= N(RL X ) = X 因此我們只要知道 S X L X 或 S X R X 的步數 ( 若 X 為奇數, 則先求 N(R X ); 若 X 為偶數, 則先求 N(L X )), 便可知道整個調換過來總共需要幾個步驟由以上觀察知總共所需步數 N(E X ) 為 : N(E X ) = N(R X ) + X + N(L X ) = 2 N(R X ) + X 所以以下就是要探討如何得知 N(R X ) 或 N(L X ) 值之過程當 X = 1 時 : 顯然 N(L 1 ) = 1 ; 而 N(R 1 ) = 2 當 X = 2 時 : 將最兩側的棋子固定不動, 則中間的 1 黑 1 白及 1 空格則視為 X = 1 情形 : _ 此時必須要到達 R 1 而不是 L 1 ( 這是因為若是 L 1 狀態, 即 : _ 則必須把最左邊的白棋往右移, 這樣雖可達到自身的 L 2 狀態, 即 : _, 但無法造成黑白交錯, 而且也無法再繼續移動下去 ) 故必須要達到 R 1 狀態, 即 _ : 其中 N(R 1 ) = 2 接著將最右邊的向左移一步, 則達到自身的 R 2 狀態, 即 _, 故 :N(R 2 ) = N(R 1 ) + 1 = = 3 步當 X = 3 時 : 仍將最兩側的棋子固定不動, 中間的 2 黑 2 白及 1 空格視為 X = 2 情形 : _ 此時必須要到達 L 2 而不是只到 R 2 ( 理由同前, 若是 R 2 狀態, 即 : _, 則最右邊的往左移後, 雖可達到 R 3 狀態, 即 : _, 但此時已無法再作任何移動 ) ~5~

6 故若中間的五格已達到 L 2 狀態, 即 : _, 則只要把最左邊的向右移一位, 則達到自身的 L 3 狀態, 即 :_ 因為 N(L 2 ) = N(R 2 ) + 2 = = 5 故 N(L 3 ) = N(L 2 ) + 1 = = 6 當 X = 4 時 : 仍將最兩側的棋子固定不動, 中間的 3 黑 3 白及 1 空格視為 X = 3 情形 : _ 此時必須要到達 R 3 而不是只到 L 3 ( 理由同前, 不再贅述 ) 即變成 : _ 最右邊的向左移一步, 則達到自身的 R 4 狀態, 即 _ 故 N(R 4 ) = N(R 3 ) + 1 = N(L 3 ) = = 10 步由以上討論, 可得以下規律 : N(L 1 ) = 1, N(R 1 ) = 2 N(R 2 ) = N(R 1 ) + 1 = = 3 N(L 3 ) = N(L 2 ) + 1 = ( N(R 2 ) + 2 ) + 1 = = 6 N(R 4 ) = N(R 3 ) + 1 = ( N(L 3 ) + 3 ) + 1 = ( ) + 1 = 10 ( 即 ) N(L 5 ) = N(L 4 ) + 1 = ( N(R 4 ) + 4 ) + 1 = ( ) + 1 = 15( 即 ) 同理類推下去, 可知 : N(L X ) = X = X ( X + 1) 2 故得出黑白各 X 個棋子, 中間 1 個空格的交換步數公式為 : X ( X + 1) N(E X ) = N(R X ) + X + N(L X ) = 2 N(R X ) + X = 2 + X = X 2 + 2X ( 二 ) 假設中間中間空格空格數為 Y, 二邊黑白棋黑白棋個數個數仍相同為 X _ _ 2 共 Y 個今將上面的圖形要移動成為 _ _ _ 共 Y 1 個 ~6~

7 即最左邊有 Y 1 個空格, 接著依序是 X 個棋 1 個空格 X 個棋由於每一個棋都要移動 ( Y 1 ) 步, 故 X 個棋總共要 X( Y 1 ) 步根據在 ( 一 ) 段中的討論, 要將之移成為 :_ _ _ 共 Y 1 個即中間 1 空格條件下, 黑白交換共須 X 2 + 2X 步最後將所有棋全部再移回最左邊, 一樣仍須 X( Y 1 ) 步 _ _ 共 Y 個故全部對調總共需要 X( Y 1 ) + X 2 + 2X + X( Y 1 ) = X 2 + 2XY 步 ( 三 ) 接著探討白棋有 X 個, 黑棋有 Y, 空格為 1 時的情形 <1> 由於情形比較複雜, 所以用歸納法來得出結果為方便起見, 我們先控制 X 跟 Y 都差 1 的情形今將 (1) X = 1, Y = 2 (2)X = 2, Y = 3 (3)X = 3, Y = 4 (4)X = 4, Y = 5 的四種移動情形列表如下 : (1) 當 X = 1, Y = 2 時 : (2) 當 X = 2, Y = 3 時 : X = 1, Y = 2 X = 2, Y = 3 步數 _ 步數 _ 1 1 _ 2 2 _ 3 3 _ 4 4 _ 5 5 _ 6 _ 7 _ 8 _ 9 _ 10 _ 11 _ ~7~

8 (3) 當 X = 3, Y = 4 時 : 步數 X = 3, Y = 4 _ 1 _ 2 _ 3 _ 4 _ 5 _ 6 _ 7 _ 8 _ 9 _ 10 _ 11 _ 12 _ 13 _ 14 _ 15 _ 16 _ 17 _ 18 _ 19 _ 完成了 (4) 當 X = 4, Y = 5 時 : 步數 X = 4, Y = 5 _ 1 _ 2 _ 3 _ 4 _ 5 _ 6 _ 7 _ 8 _ 9 _ 10 _ 11 _ 12 _ 13 _ 14 _ 15 _ 16 _ 17 _ 18 _ 19 _ 20 _ 21 _ 22 _ 23 _ 24 _ 25 _ 26 _ 27 _ 28 _ 29 _ 完成了 ~8~

9 我們再將其他情形都實際完成後, 紀錄其步數 ( 因過程繁複, 此處不列出完整過程 ), 實驗表列如下 : X Y 步數與前項差數無若我們以 F(X) 代表在 X 個白棋,X + 1 個黑棋的情況下, 交換所需的步數, 則可得 :F(1) = 5 F(2) = F(1) = F(3) = F(2) = F(4) = F(3) = F(X) = F(X 1) + 2( X 1 ) + 4 所增步數 = 2 (X 1) + 4 = 2X + 2 將所有等式相加得 : F(1) + F(2) + + F(X 1) + F(X) = 5 + F(1) + F(2) + + F(X 1) + ( (2X + 2) ) 因兩邊都有 F(1) + F(2) + + F(X 1), 消去後得 : F(X) = 5 + ( ( 2X + 2 )) = 5 + 有 X 1 項 = 5 + ( X 1 )( X + 4 ) = 5 + X 2 + 3X 4 = X 2 + 3X + 1 ~9~ ( X 1 )( 6+ ( 2X + 2 )) ( X )( X + = + ) 2 2 <2> 接著我們探討 X 與 Y 相差 2 的情形, 我們只列出比較小的情形 : (1) X = 1, Y = 3 (2)X = 2, Y = 4 (3)X = 3, Y = 5 等三種移動情形其他數字較大者, 我們有實際操作過, 而將結果紀錄下來 (1) 當 X = 1, Y = 3 時 : (2) 當 X = 2, Y = 4 時 : X = 1, Y = 3 X = 2, Y = 4 步數 _ 步數 _ 1 1 _ 2 2 _ 3 3 _

10 4 4 _ 5 5 _ 6 6 _ 7 7 _ 8 _ 9 _ 10 _ 11 _ 12 _ 13 _ 14 _ (3) 當 X = 3, Y = 5 時 : 步數 X = 3, Y = 5 _ 1 _ 2 _ 3 _ 4 _ 5 _ 6 _ 7 _ 8 _ 9 _ 10 _ 11 _ 12 _ 13 _ 14 _ 15 _ 16 _ 17 _ 18 _ 19 _ 20 _ 21 _ 22 _ 23 _ 完成了我們再將其他情形都實際完成後, 紀錄其步數 ( 因過程繁複, 此處不列出完整過程 ), 實驗表列如下 : X Y 步數與前項差數無 ~10~

11 若我們以 G(X) 代表在 X 個白棋,X + 2 個黑棋的情況下, 交換所需的步數, 則可得 :G(1) = 7 G(2) = G(1) = G(3) = G(2) = G(4) = G(3) = G(X) = G(X 1) + 2( X 1 ) + 5 所增步數 = 2 (X 1) + 5 = 2X + 3 將所有等式相加得 : G(1) + G(2) + + G(X 1) + G(X) = 7 + G(1) + G(2) + + G(X 1) + ( (2X + 3)) 因兩邊都有 G(1) + G(2) + + G(X 1), 消去後得 : G(X) = 7 + ( ( 2X + 3 )) = 7 + 有 X 1 項 = 7 + ( X 1 )( X + 5 ) = 7 + X 2 + 4X 5 = X 2 + 4X + 2 ( X 1 )( 7+ ( 2X + 3 )) ( X )( X + = + ) 2 2 <3> 接著我們探討 X 與 Y 相差 3 的情形, 由於篇幅關係, 我們不再把經過情形列出, 只把我們實際操作後的結果紀錄下來, 如下表列 : X Y 步數與前項差數無若我們以 H(X) 代表在 X 個白棋,X + 3 個黑棋的情況下, 交換所需的步數, 則可得 :H(1) = 9 H(2) = H(1) = H(3) = H(2) = H(4) = H(3) = H(X) = H(X 1) + 2( X 1 ) + 6 所增步數 = 2 (X 1) + 6 = 2X + 4 ~11~

12 將所有等式相加得 : H(1) + H(2) + + H(X 1) + H(X) = 9 + H(1) + H(2) + + H(X 1) + ( (2X + 4)) 因兩邊都有 H(1) + H(2) + + H(X 1), 消去後得 : H(X) = 9 + ( ( 2X + 4 )) = 9 + 有 X 1 項有 X 1 項 = 9 + ( X 1 )( X + 6 ) = 9 + X 2 + 5X 6 = X 2 + 5X + 3 有 X+1 項 X ( 3+ ( 2X + 1)) 2 ~12~ ( X 1 )( 8+ ( 2X + 4 )) ( X )( X + = + ) 2 2 <4> 最後我們要找一般性的規律 : 當 X, Y 相差 1 時 : 第一項 F(1) = 5 = , 第二項 F(2) 比 F(1) 多 6 = 1 + 5, 以後固定差 2 當 X, Y 相差 2 時 : 第一項 G(1) = 7 = , 第二項 G(2) 比 G(1) 多 7 = 2 + 5, 以後固定差 2 當 X, Y 相差 3 時 : 第一項 H(1) = 9 = , 第二項 H(2) 比 H(1) 多 8 = 3 + 5, 以後固定差 2 依此類推, 若有 X 個白棋,Y 個黑棋, 即相差 ( Y X ) 個時, 則 : 第一項 A(1) = 2 ( Y X ) + 3, 第二項 A(2) 比 A(1) 多 (Y X)+5, 以後固定差 2 故得 A(1) = 2 ( Y X ) + 3 A(2) = A(1) + ( Y X ) = A(3) = A(2) + ( Y X ) = A(4) = A(3) + ( Y X ) = 將所有等式相加得 : A(X) = A(X 1) + ( Y X ) + 2 (X 1 ) + 3 所增步數 = 2 (X 1) + 3 A(1) + A(2) + + A(X 1) + A(X) = 2 ( Y X ) A(1) + A(2) + + A(X 1) + ( Y X ) + ( Y X ) + + ( Y X ) + ( ( 2X + 1 ) 有 X 1 項因兩邊都有 A(1) + A(2) + + A(X 1), 消去後得 : A(X) = ( Y X ) + ( Y X ) + + ( Y X ) + ( ( 2X + 1 ) = ( X + 1 )( Y X ) + = XY + X + Y 有 X 項 = XY X 2 + Y X + X( X + 2 )

13 ( 四 ) 接著要探討最一般化的情形 : 白棋有 X 個, 黑棋有 Y 個, 空格有 Z 個 : _ _ 有 X 個有 Z 個有 Y 個採用類似第 ( 二 ) 段時移動的方法, 將左邊的全部移動到中間只剩 1 個空格, 每個都需要移動 ( Z 1 ) 步, 而 X 個總共需要 X( Z 1 ) 步, 此時成為 _ _ _ 有 Z 1 個有 X 個有 Y 個利用第 ( 三 ) 段的結論, 在中間有 1 個空格的情況下, 要將黑白棋對調過來需要 XY + X + Y 步, 此時成為 :_ _ _ 有 Z 1 個有 Y 個有 X 個接著將棋全部移回最左邊, 每個都需要移動 ( Z 1 ) 步, 而 Y 個總共需要 Y( Z 1 ) 步, 此時就是完成的狀態了即 _ _ 故總共所需要的步數為 : X( Z 1 ) + XY + X + Y + Y( Z 1 ) = XY + YZ + ZX 這就是我們最後所要的結論了肆結論 : 一左邊有 X 個白色棋子, 右邊亦有 X 個黑色棋子, 中間有 1 個空格不同顏色的棋子可以跳躍過去, 同顏色的棋子不可以跳躍在此條件下, 要把不同顏色交換過來, 需要 X 2 +2X 步二左邊有 X 個白色棋子, 右邊亦有 X 個黑色棋子, 中間有 Y 個空格在上述規則限制下, 要把不同顏色交換過來, 最少需要 X 2 +2XY 步三左邊有 X 個白色棋子, 右邊有 Y 個黑色棋子, 中間有 1 個空格在上述規則限制下, 要把不同顏色交換過來, 最少需要 XY+X+Y 步四左邊有 X 個白色棋子, 右邊有 Y 個黑色棋子, 中間有 Z 個空格在上述規則限制下, 要把不同顏色交換過來, 最少需要 XY+YZ+ZX 步 ~13~

14 伍研究展望 : 我們希望能繼續研究成平面, 如下圖, 並可分成走斜線及不可走斜線等條件進行推演歸納, 期望一樣能找出公式陸參考資料一何珍梅等編 (1995 新版 ) 國民小學數學第 10 冊 ( 五下 ) 第 7 單元怎樣解題台南 : 南一二何珍梅等編 (1995 新版 ) 國民小學數學第 11 冊 ( 六下 ) 第 9 單元怎樣列式台南 : 南一三查孟華譯 (1996) 數學推敲 : 計數二頁新竹 : 凡異 ~14~

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

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