1

摘要 有一次和同學在網路上發現了 青蛙跳 這個遊戲, 大家絞盡腦汁就為了比別人花更少步數完成此遊戲, 每個人都有不同的想法, 於是我們決定以數學的方式找出此遊戲各步數比的最少步數公式和移動方法 根據推論和規納後發現以下結果 : 一 當兩邊棋數相同時, 假設其中一邊的棋數為 n, 則最少步數為 : 2n+n 2 二 當兩邊棋數相同時, 移動方法為 : 1. 將最後位置畫在紙上 2. 將 m 和 j 的頻率寫在紙上 3. 將左右棋子移動頻率寫在紙上 4. 將步驟 2 3 相互對照, 移動棋子 5. 對照步驟 1 所畫的最後位置, 檢查位置是否正確 三 當兩邊棋數為 1:w 且 w 為偶數時最少步數為 (w 2 +2w+2)/2 步四 當兩邊棋數為 1:w 且 w 為奇數時最少步數為 (w 2 +2w+3)/2 步五 當棋數比 2:w, w 為偶數, 最少步數為 :(w 2 +2w+8)/2 步六 當棋數比 2:w, w 為奇數, 最少步數為 :(w 2 +2w+9)/2 步七 當棋數比 3:w, w 為偶數, 最少步數為 :(w 2 +2w+16)/2-1 步八 當棋數比 3:w, w 為奇數, 最少步數為 :(w 2 +2w+17)/2-1 步 1

壹 研究動機老師介紹一個數學網站, 我和同學在上面發現了 青蛙互跳 這個遊戲, 對此感到好奇, 希望藉由數學的方法找出有關此遊戲的數學原理, 減少遊戲時所耗損的時間 貳 研究目的一 兩邊棋數相同時, 推導出以最少步數完成此遊戲的步數公式 二 兩邊棋數相同時, 找出以最少步數完成此遊戲的方法 三 兩邊棋數不同時, 找出最少 黑白棋 紙 筆 参 研究設備及器材 肆 研究過程及方法一 名詞解釋 ( 一 ) 步法 走 : 棋子向右或左移動一格 舉例來說如下, 白棋向左移動一格, 即白棋向左 走 一格 步數排列方式起始變成第 1 步 ( 二 ) 步法 跳 : 當一棋子右邊 1 格或左邊 1 格有棋子時, 越過右邊 1 格或左邊 1 格的棋子移動, 並落在右邊 1 格或左邊 1 格棋子的前方空格, 即為步法 跳, 舉例如下 步數排列方式起始變成第 1 步 ( 三 ) 移動 : 包含步法 走 和步法 跳 ( 四 ) 最少步數走法 : 以最少的移動次數完成此遊戲 ( 五 )Ln: 最初在左邊的棋子們 ( 不用同一顆 ) 連續移動 ( 走或跳 ) 了 n 次的步數方法就記為 Ln ( 六 )Rn: 最初在右邊的棋子們 ( 不用同一顆 ) 連續移動 ( 走或跳 ) 了 n 次的步數方法就記為 Rn ( 七 ) 青蛙互跳 遊戲規則 : 黑子 ( 數量不限 ) 置於右邊排成一列, 白子 ( 數量不限 ) 置於左邊排成一列, 兩種顏色棋子中間空一格空位, 可移動任何一顆棋子, 使其 走 一步或 跳 一步, 以最少步數使黑白棋左右互換 ( 如圖 4-1 4-2) 2

步 數 排 列 方 式 起 始 第 1 步 第 2 步 接續下去 第 n 步 圖 4-1 步 數 排 列 方 式 起 始 第 1 步 第 2 步 接續下去 第 n 步 圖 4-2 二 研究研究過程為了觀察及記錄其規律, 兩邊棋子分別以英文字母大寫和小寫表示, 起始時在最外側兩邊的棋子分別以大寫 A 和小寫 a 開始依序表示, 以此類推 ( 一 ) 兩邊棋數相同相同時, 移動所需所需最少步數 1. 兩邊棋數 1:1 的步數 在兩邊棋數 1:1 的情況下, 經過嘗試後, 發現最少步數走法為 3 步 ( 如圖 4-3) 步 數 排列方式 起 始 A a 第 1 步 A a 第 2 步 a A 第 3 步 a A 圖 4-3 兩邊棋數 1:1 的步數及排列方式圖 2. 兩邊棋數 2:2 的步數 在兩邊棋數 2:2 的情況下, 經過嘗試後, 發現最少步數走法為 8 步 ( 如圖 4-4) 步數排列方式起始 A B b a 第 1 步 A B b a 3

第 2 步 A b B a 第 3 步 A b B A 第 4 步 b A B a 第 5 步 b A a B 第 6 步 b A a B 第 7 步 b a A B 第 8 步 b a A B 圖 4-4 兩邊棋數 2:2 的步數及排列方式圖 3. 兩邊棋數 3:3 的步數在兩邊棋數 3:3 的情況下, 經過嘗試後, 發現最少步數走法為 15 步 ( 如圖 4-5) 步數排列方式起始 A B C a b c 第 1 步 A B C a b c 第 2 步 A B a C b c 第 3 步 A B a C b c 第 4 步 A a B C b c 第 5 步 A a B b C c 第 6 步 A a B b C c 第 7 步 A a B b c C 第 8 步 A a b B c C 第 9 步 a A b B c C 第 10 步 a A b B c C 第 11 步 a b A B c C 第 12 步 a b A c B C 第 13 步 a b A c B C 第 14 步 a b c A B C 第 15 步 a b c A B C 圖 4-5 兩邊棋數 3:3 的步數及排列方式圖 4. 兩邊棋數 n:n 的步數按照上面類似方法可試出兩邊棋數比為 4:4 5:5 6:6 等, 其最少步數如下 : 1:1 為 3 步, 2:2 為 8 步, 3:3 為 15 步, 4:4 為 24 步, 5:5 為 35 步, 6:6 為 48 步, ( 二 ) 兩邊棋數相同相同時, 移動最少步數的公式規律規律及移動步驟移動步驟方法根據以上數據和圖形中的規律, 我們找出了幾樣規則 : 1. 假設 走 的步數為 s 步, 跳 的步數為 t 步, 兩邊各有 n 顆棋, 則 s=n+n=2n t= 4

(2n/2) 2 =n 2, 移動總步數 ( 包含 走 和 跳 )=s+t=2n + n 2, 舉例如下圖 4-6 兩邊棋數比 s( 走 的步數) t( 跳 的步數) 1:1 2 1 2:2 4 4 3:3 6 9 4:4 8 16 5:5 10 25 6:6 12 36 圖 4-6 棋數比 s 與 t 關係圖 棋數為 1:1,s=2n=2 1=2,t=1 2 =1, 移動總步數 =2+1=3 棋數為 2:2,s=2n=2 2=4,t=2 2 =4, 移動總步數 =4+4=8 棋數為 3:3,s=2n=2 3=6,t=3 2 =9, 移動總步數 =6+9=15 棋數為 4:4,s=2n=2 4=8,t=4 2 =16, 移動總步數 =8+16=24 棋數為 5:5,s=2n=2 5=10,t=5 2 =25, 移動總步數 =10+25=35 棋數為 6:6,s=2n=2 6=12,t=6 2 =36, 移動總步數 =12+36=48 2. 在說明此發現之前, 先解釋幾個符號,L= 左 R= 右,Ln 的意思就是最初在左邊的棋子們 ( 不用同一顆 ), 連續移動 ( 走或跳 ) 了 n 次,Rn 的意思就是最初在右邊的棋子 ( 不用同一顆 ), 連續移動 ( 走或跳 ) 了 n 次 假設一邊有 n 顆棋, 一開始從右邊的棋子移動, 我們發現了左右棋子的移動頻率會呈現金字塔型, 兩邊棋子移動的順序關係如下, n 為偶數 :Y=R X=L R1L2 Xn Yn Xn...L2 R1 n 為奇數 :Y=L X=R 舉例來說 : (1) 棋數 1:1 時 R1 L1 R1,n=1( 奇數 ),Y=L X=R (2) 棋數 2:2 時 R1 L2 R2 L2 R1,n=2( 偶數 ),Y=R X=L (3) 棋數 3:3 時 R1 L2 R3 L3 R3 L2 R1,n=3( 奇數 ),Y=L X=R (4) 棋數 4:4 時 R1 L2 R3 L4 R4 L4 R3 L2 R1,n=4( 偶數 ),Y=R X=L 綜合言之, 不管棋數 5:5 6:6 或 n:n 也具有以上規則, 步數繁多, 故不列出 5

( 三 ) 兩邊棋數相同時, 移動最少步數的方法 1. 假設一邊有 n 顆棋, 則任意一顆棋子和它最後停止的點有以下關係 : 如果一開始時是在左邊, 最後停止的點會是向右走 n+1 格, 如果一開始是在右邊, 最後停止的點會是向左走 n+1 格 2. 令 走 為 m, 跳 為 j, 則 m 和 j 出現順序的關係如下 : 假設一邊有 n 顆棋, 走 m 步並不會連續出現, 但必會在頭尾出現, 而 跳 j 步則在 走 m 步之後出現, 再第一個 走 m 步和第 2 個 走 m 步之間出現的 跳 j 步只有 1 個, 在第 2 個 走 m 步和第 3 個 走 m 步之間會連續出現 2 個 跳 j 步, 在第 n 個 走 m 步和第 n+1 個 走 m 步之間會連續出現 n 個 跳 j 步, 直到 n+1 個 走 m 步和 n+2 個 走 m 步之間會連續出現 n-1 個 跳 j 步, 在 n+2 個 走 m 步和 n+3 個 走 m 步之間會連續出現 n-2 個 跳 j 步, 最後一直到只有一個 跳 j 步為止 如下所示 : (1) 當棋數是 1:1 時( 即 n=1), 則 mjm j 的出現頻率為 1 (2) 當棋數是 2:2 時( 即 n=2), 則 m j m jj m j m, j 的出現頻率為 1 2 1, 總結 : 第 1 和 2 個 m 之間出現 1 個 j, 第 2( 第 n) 和第 3( 第 n+1) 個 m 之間出現 2 個 (n 個 )j, 第 3( 第 n+1) 和第 4(n+2) 個 m 之間出現 1 個 (n-1) 個 j (3) 當棋數是 3:3 時( 即 n=3), 則 m j m jj m jjj m jj m j m, j 的出現頻率為 1 2 3 2 1 總結 : 第 1 和 2 個 m 之間出現 1 個 j, 第 2 和第 3 個 m 之間出現 2 個 j, 第 3( 第 n) 和第 4(n+1) 個 m 之間出現 3 個 (n 個 )j, 第 4(n+1) 和第 5(n+2) 個 m 之間出現 2 個 (n-1 個 )j, 第 5(n+2) 和第 6(n+3) 個 m 之間出現 1 個 (n-2 個 )j 綜合以上, 不管棋數是 4:4 5:5 6:6 或 n:n, 都會遵守上述定律, 因步 數繁雜, 故不一一列出 ( 四 ) 兩邊棋數不同時 ( 棋數 1:w), 移動最少步數的公式規律及移動步驟方法 1. 兩邊棋數不相同 ( 棋數 1:w) 的移動步數 6

根據操作後發現各棋數比和對應的最少步數和關係如下圖 4-7: 兩邊棋數比 最少步數 1:2 5 1:3 9 1:4 13 1:5 19 1:6 25 1:7 33 1:8 41 1:9 51 1:10 61 圖 4-7 兩邊棋數 1:w 和對應的最少步數和關係圖 2. 兩邊棋數不相同 ( 棋數 1:w) 的移動步驟方法我們以兩邊棋數相同時的推論方法來推論 (1) 令走為 s, 跳為 t, 棋數比為 1 比 w s t 和 w 沒有任何關係 (2) 最初位置和最後位置的討論當棋數比 1:2 時, 起始位置為 a AB, 最後位置為 BA a 當棋數比 1:3 時, 起始位置為 a ABC, 最後位置為 BCA a 當棋數比 1:4 時, 起始位置為 a ABCD, 最後位置為 DBCA a 最初位置和最後位置並無規律 (3) 走 m 步和 跳 j 步的順序關係當棋數比 1:2 時,m 和 j 的移動順序 : mjmjj 當棋數比 1:3 時,m 和 j 的移動順序 : mjmjjmmjj 當棋數比 1:4 時,m 和 j 的移動順序 : mjmjjmjjjjmjj m 和 j 的移動順序並無任何關係 (4) 左邊的棋子和右邊的棋子移動順序 ( 棋數比 1:w) 當棋數比 1:2 時, R1 L1 R3 當棋數比 1:3 時, R1 L1 R7 當棋數比 1:4 時, R1 L1 R11 當棋數比 1:5 時, R1 L1 R17 必定是 R1 L1 Rx,x 依照 4 4 6 6 8 8 10 10 的數列加上去 7

(5) 兩邊棋數比 1:w 的結論因為當棋數比 1:w 時, 沒有一些固定且有規律的關係, 所以我們只好以各棋數比的最少步數之間的關係來推算 棋數比其中一邊為 1, 假設另一邊為 w, 則此棋數比的最少步數公式為 : w 為奇數 (w 2 +2w+3)/2 w 為偶數 (w 2 +2w+2)/2 推導過程 : 前一個棋數比和後一個棋數比的最少步數差的數列為 : 4 4 6 6 8 8 10 10.. 發現此數列類似等差數列, 只是一個項重複 2 次, 所以最後要乘 2, 已知棋數比 1:2 時, 最少步數為 5 步, 所以最後要加上 5,w 為偶數時, 因為一個同樣的數字會加兩次, 表示已經出現了 (w-2)/2 個數字 第 (w-2)/2 項, 依等差級數公式 S n =n 2a 1 +d(n-1) /2, 可得最少步數公式為 5+2 (w-2)/2 (8+2 ((w-2)/2-1)) /2=(w 2 +2w+2)/2 當 w 為奇數時, 令 m 為 w-1, 則最少步數為 (m 2 +2m+2)/2, 代入 w-1 後 =(w 2 +1)/2, 而 w 本身加的步數為 2 (w-1)/2-1 +4, 最少步數公式為 :(w 2 +1)/2+2 (w-1)/2-1 +4=(w 2 +2w+3)/2 ( 五 ) 兩邊棋數不同時 ( 棋數 2:w), 移動最少步數的公式規律及移動步驟方法 根據操作後發現各棋數比和對應的最少步數和關係如圖 4-8: 兩邊棋數比 最少步數 2:2 8 2:3 12 2:4 16 2:5 22 2:6 28 2:7 36 2:8 44 2:9 54 2:10 64 圖 4-8 兩邊棋數 2:w 和對應的最少步數和關係圖 發現到當兩邊棋數 2:w 時, 前一個棋數比和後一個棋數比的最少步數差的數列為 4 4 6 6 8 8 10 10.., 跟兩邊棋數 1 比 w 時一樣, 所以公式自然一樣, 只是第一個棋數比的最少步數不是 5, 而是 8, 當 w 為偶數時最少步數公式變成 : 8+2 (w-2)/2 (8+2 (w-2)/2-1) /2=(w 2 +2w+8)/2 8

而當 w 為偶數時, 最少步數公式變成 : (w 2 +7)/2+2 (w-1)/2-1 +4=(w 2 +2w+9)/2 ( 六 ) 兩邊棋數不同時 ( 棋數 3:w), 移動最少步數的公式規律及移動步驟方法 兩邊棋數比不相同的移動方法與討論 ( 棋數比 3:w) 根據操作後發現各棋數比和對應的最少步數和關係如圖 4-9: 兩邊棋數比 最少步數 3:2 12 3:3 15 3:4 19 3:5 25 3:6 31 3:7 39 3:8 47 3:9 57 3:10 67 圖 4-9 兩邊棋數 3:w 和對應的最少步數和關係圖 發現到當兩邊棋數 3:w 時, 前一個棋數比和後一個棋數比的最少步數差的數列為 3 4 6 6 8 8 10 10.., 這時候我們也可以依照上面推算棋數比 1:w 和 2:w 最少步數 公式的方法進行推算, 只是最後要減掉 1, 因為棋數比 3:w 時第一個棋數比和第二個棋數比 的最少步數差的為 3, 不是 4, 還有第一個棋數比的最少步數是 12, 不是 5 或 8, 依據上述條 件, 我們可以推出棋數比 3:w 時最少步數公式為 : w 為奇數 (w 2 +2w+17)/2-1 w 為偶數 (w 2 +2w+16)/2-1 9

一 兩邊棋數相同兩邊棋數相同討論 伍 討論討論與結論 根據上面發現的 4 條規則, 可以找出最少步數的公式和移動方法 : ( 一 ) 最少步數公式 1. 根據第 1 個發現 : 走 的步數為 s, 跳 的步數為 t, 全部有 2n 顆棋, 則 s=2n t=n 2, 可推出最少步數為 s+t=2n+n 2 2. 根據第 4 個發現 :R1L2 Xn Yn Xn...L2 R1 可發現兩邊的紅字分別為兩等差級 數, 再加上最中間的 n( 假設 w), 即為最少步數, 公式為 : a 1 =1 d=1 a n =w n=(w-1)/1+1=w 所以依據 S n = n (a 1 + a n ) /2 可推出 : 最少步數 =2 w (1+ w) /2+w=2w+w 2 ( 二 ) 移動方法分為幾個步驟 : 1. 依照發現 2 將最後位置畫在紙上 2. 依照發現 3 將 m 和 j 的頻率寫在紙上 3. 依照發現 4 將左右棋子移動頻率寫在紙上 4. 將步驟 2 3 相互對照, 移動棋子 5. 對照步驟 1, 檢查位置是否正確 ( 三 ) 移動方法的實際操作 : 棋數 4:4 先代入公式 2 4+4 2 =24 依據公式來看最少步數為 24 步, 根據移動方法來操作, 是 否為 24 步? 1. n=4 時, 左邊向右移 5 格, 右邊向左移 5 格 A B C D d c b a 最後位置 d c b a A B C D 2. n=4 時, m 和 j 出現順序為 m j m jj m jjj m jjjj m jjj m jj m j m 3. n=4 時, R1 L2 R3 L4 R4 L4 R3 L2 R1 4. m j m jj m jjj m jjjj m jjj m jj m j m R1 L2 R3 L4 R4 L4 R3 L2 R1 R1 代表右邊的棋子移動一次, 對應的是上排的第一步, 也就是 m,l2 代表左邊的棋子移 動兩次, 對應的是上排的第二 三步, 也就是 j m, 其餘依此類推 綜合以上, 經過操作後, 發現果然可以在 24 步走完且和步驟 1 所畫出的最後圖形符合, 證明我們的移動方法正確 ( 如圖 5-1) 10

步數排列方式起始 A B C D d c b a 第 1 步 A B C D d c b a 第 2 步 A B C d D c b a 第 3 步 A B C d D c b a 第 4 步 A B d C D c b a 第 5 步 A B d C c D b a 第 6 步 A B d C c D b a 第 7 步 A B d C c b D a 第 8 步 A B d c C b D a 第 9 步 A d B c C b D a 第 10 步 A d B c C b D a 第 11 步 d A B c C b D a 第 12 步 d A c B C b D a 第 13 步 d A c B b C D a 第 14 步 d A c B b C a D 第 15 步 d A c B b C a D 第 16 步 d A c B b a C D 第 17 步 d A c b B a C D 第 18 步 d c A b B a C D 第 19 步 d c A b B a C D 第 20 步 d c b A B a C D 第 21 步 d c b A a B C D 第 22 步 d c b A a B C D 第 23 步 d c b a A B C D 第 24 步 d c b a A B C D 圖 5-1 兩邊棋數 4:4 的步數及排列方式圖 二 兩邊棋數相同兩邊棋數相同結論第一點歷屆科展就已經有人發現過了, 於是我們把它繼續做延伸, 找出了移動方法和部分兩邊棋數不相同的最少步數公式 ( 第 2 到 8 點 ), 未來希望能再進一步找出兩邊棋數比 v:w 的最少步數公式 1. 當兩邊棋數相同時, 假設其中一邊的棋數為 n 則最少步數為 : 2n+n 2 2. 當兩邊棋數相同時, 移動方法為 : (1) 將最後位置畫在紙上 (2) 將 m 和 j 的頻率寫在紙上 (3) 將左右棋子移動頻率寫在紙上 (4) 將步驟 2 3 相互對照, 移動棋子 (5) 對照步驟 1 所畫的最後位置, 檢查位置是否正確 11

3. 當兩邊棋數為 1:w 且 w 為偶數時最少步數為 (w 2 +2w+2)/2 4. 當兩邊棋數為 1:w 且 w 為奇數時最少步數為 (w 2 +2w+3)/2 5. 當棋數比 2:w, w 為偶數, 最少步數為 :(w 2 +2w+8)/2 6. 當棋數比 2:w, w 為奇數, 最少步數為 :(w 2 +2w+9)/2 7. 當棋數比 3:w, w 為偶數, 最少步數為 :(w 2 +2w+16)/2-1 8. 當棋數比 3:w, w 為奇數, 最少步數為 :(w 2 +2w+17)/2-1 陸 參考參考資料一 莊志宏 勇往直前 - 一個遊戲的數學分析 育達學報 二 許志農 ( 民 97) 動手玩數學 龍騰數亦優,27 頁 12