高雄市 96 年度國小學生獨立研究成果發表競賽 作品說明書 類別 : 數學類 作品名稱 : 乾坤大挪移 - 最少步數之探討 學校 : 愛國國小 研究者 : 蔡惟名 王冠承 陳淇鈺 廖宜威 謝富丞 陳柏勳 指導老師 : 曹秀美 張家慶 ~1~
乾坤大挪移 ~ 最少步數之探討 摘要 下課時, 我們常在教室後面的益智區玩跳棋, 要將棋子以最快的速度, 也就是最少的步數移到對面才能贏對方, 不服輸的我們, 常常為了要贏棋而絞盡腦汁 所以就想要研究同一條直線下, 如何以最少的步數, 把二個不同顏色的棋子對調 結果發現 : 一 左邊有 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~
乾坤大挪移 ~ 最少步數之探討 壹 研究研究動機 下課時, 我們常在教室後面的益智區玩跳棋, 要將棋子以最快的速度, 也就是最少的步數移到對面才能贏對方, 不服輸的我們, 常常為了要贏棋而絞盡腦汁 所以就想要研究同一條直線下, 如何以最少的步數, 把二個不同顏色的棋子對調, 於是請老師帶領我們做這個研究 貳 研究目的 一 左邊有 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~
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~
我們發現到 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 = 2 + 1 = 3 步當 X = 3 時 : 仍將最兩側的棋子固定不動, 中間的 2 黑 2 白及 1 空格視為 X = 2 情形 : _ 此時必須要到達 L 2 而不是只到 R 2 ( 理由同前, 若是 R 2 狀態, 即 : _, 則最右邊的 往左移後, 雖可達到 R 3 狀態, 即 : _, 但此時已無法再作任何移動 ) ~5~
故若中間的五格已達到 L 2 狀態, 即 : _, 則只要把最左邊的 向右移一位, 則達到自身的 L 3 狀態, 即 :_ 因為 N(L 2 ) = N(R 2 ) + 2 = 3 + 2 = 5 故 N(L 3 ) = N(L 2 ) + 1 = 5 + 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 ) + 3 + 1 = 6 + 3 + 1 = 10 步由以上討論, 可得以下規律 : N(L 1 ) = 1, N(R 1 ) = 2 N(R 2 ) = N(R 1 ) + 1 = 2 + 1 = 3 N(L 3 ) = N(L 2 ) + 1 = ( N(R 2 ) + 2 ) + 1 = 3 + 2 + 1 = 6 N(R 4 ) = N(R 3 ) + 1 = ( N(L 3 ) + 3 ) + 1 = ( 6 + 3 ) + 1 = 10 ( 即 1 + 2 + 3 + 4 ) N(L 5 ) = N(L 4 ) + 1 = ( N(R 4 ) + 4 ) + 1 = ( 10 + 4 ) + 1 = 15( 即 1 + 2 + 3 + 4 + 5) 同理類推下去, 可知 : N(L X ) = 1 + 2 + 3 + + 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~
即最左邊有 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~
(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~
我們再將其他情形都實際完成後, 紀錄其步數 ( 因過程繁複, 此處不列出完整過程 ), 實驗表列如下 : X Y 步數與前項差數 1 2 5 無 2 3 11 6 3 4 19 8 4 5 29 10 5 6 41 12 若我們以 F(X) 代表在 X 個白棋,X + 1 個黑棋的情況下, 交換所需的步數, 則 可得 :F(1) = 5 F(2) = F(1) + 6 6 = 2 1 + 4 F(3) = F(2) + 8 8 = 2 2 + 4 F(4) = F(3) + 10 10 = 2 3 + 4. 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) + ( 6 + 8 + + (2X + 2) ) 因兩邊都有 F(1) + F(2) + + F(X 1), 消去後得 : F(X) = 5 + ( 6 + 8 + + ( 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 )) 1 2 8 5 ( 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 _
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 步數 與前項差數 1 3 7 無 2 4 14 7 3 5 23 9 4 6 34 11 5 7 47 13 ~10~
若我們以 G(X) 代表在 X 個白棋,X + 2 個黑棋的情況下, 交換所需的步數, 則可得 :G(1) = 7 G(2) = G(1) + 7 7 = 2 1 + 5 G(3) = G(2) + 9 9 = 2 2 + 5 G(4) = G(3) + 11 11 = 2 3 + 5. 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) + ( 7 + 9 + + (2X + 3)) 因兩邊都有 G(1) + G(2) + + G(X 1), 消去後得 : G(X) = 7 + ( 7 + 9 + + ( 2X + 3 )) = 7 + 有 X 1 項 = 7 + ( X 1 )( X + 5 ) = 7 + X 2 + 4X 5 = X 2 + 4X + 2 ( X 1 )( 7+ ( 2X + 3 )) 1 2 10 7 ( X )( X + = + ) 2 2 <3> 接著我們探討 X 與 Y 相差 3 的情形, 由於篇幅關係, 我們不再把經過情形 列出, 只把我們實際操作後的結果紀錄下來, 如下表列 : X Y 步數 與前項差數 1 4 9 無 2 5 17 8 3 6 27 10 4 7 39 12 5 8 53 14 若我們以 H(X) 代表在 X 個白棋,X + 3 個黑棋的情況下, 交換所需的步數, 則可得 :H(1) = 9 H(2) = H(1) + 8 8 = 2 1 + 6 H(3) = H(2) + 10 10 = 2 2 + 6 H(4) = H(3) + 12 12 = 2 3 + 6. H(X) = H(X 1) + 2( X 1 ) + 6 所增步數 = 2 (X 1) + 6 = 2X + 4 ~11~
將所有等式相加得 : H(1) + H(2) + + H(X 1) + H(X) = 9 + H(1) + H(2) + + H(X 1) + ( 8 + 10 + + (2X + 4)) 因兩邊都有 H(1) + H(2) + + H(X 1), 消去後得 : H(X) = 9 + ( 8 + 10 + + ( 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 )) 1 2 12 9 ( X )( X + = + ) 2 2 <4> 最後我們要找一般性的規律 : 當 X, Y 相差 1 時 : 第一項 F(1) = 5 = 2 1 + 3, 第二項 F(2) 比 F(1) 多 6 = 1 + 5, 以後固定差 2 當 X, Y 相差 2 時 : 第一項 G(1) = 7 = 2 2 + 3, 第二項 G(2) 比 G(1) 多 7 = 2 + 5, 以後固定差 2 當 X, Y 相差 3 時 : 第一項 H(1) = 9 = 2 3 + 3, 第二項 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 ) + 5 5 = 2 1 + 3 A(3) = A(2) + ( Y X ) + 7 7 = 2 2 + 3 A(4) = A(3) + ( Y X ) + 9 9 = 2 3 + 3. 將所有等式相加得 : 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 ) + 3 + A(1) + A(2) + + A(X 1) + ( Y X ) + ( Y X ) + + ( Y X ) + ( 5 + 7 + + ( 2X + 1 ) 有 X 1 項 因兩邊都有 A(1) + A(2) + + A(X 1), 消去後得 : A(X) = ( Y X ) + ( Y X ) + + ( Y X ) + ( 3 + 5 + 7 + + ( 2X + 1 ) = ( X + 1 )( Y X ) + = XY + X + Y 有 X 項 = XY X 2 + Y X + X( X + 2 )
( 四 ) 接著要探討最一般化的情形 : 白棋有 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~
伍 研究展望 : 我們希望能繼續研究成平面, 如下圖, 並可分成走斜線及不可走斜線等條 件進行推演 歸納, 期望一樣能找出公式 陸 參考資料 一 何珍梅等編 (1995 新版 ) 國民小學數學第 10 冊 ( 五下 ) 第 7 單元 怎樣解題 台南 : 南一 二 何珍梅等編 (1995 新版 ) 國民小學數學第 11 冊 ( 六下 ) 第 9 單元 怎樣列式 台南 : 南一 三 查孟華譯 (1996) 數學推敲 : 計數二 75-77 頁 新竹 : 凡異 ~14~