目錄摘要 page 2 研究動機 page 2 研究目的 page 2 研究設備與器材 page 3 研究過程與方法 page 3 研究結果研究一 page 4 研究二 page 7 研究三 page 9 研究四 page 9 研究五 page 12 研究六 page 18 研究七 page 19

Size: px

Start display at page:

Download "目錄摘要 page 2 研究動機 page 2 研究目的 page 2 研究設備與器材 page 3 研究過程與方法 page 3 研究結果研究一 page 4 研究二 page 7 研究三 page 9 研究四 page 9 研究五 page 12 研究六 page 18 研究七 page 19"

作贤沈
5 years ago
Views:

1 高雄市 103 年度國中學生獨立研究成果發表競賽作品說明書參賽類別 : 數學類作品名稱 :Hamilton 黑白棋盤一筆劃編號 : ( 由承辦單位統一填寫 )

2 目錄摘要 page 2 研究動機 page 2 研究目的 page 2 研究設備與器材 page 3 研究過程與方法 page 3 研究結果研究一 page 4 研究二 page 7 研究三 page 9 研究四 page 9 研究五 page 12 研究六 page 18 研究七 page 19 討論 page 23 結論 page 25 未來的展望 page 26 參考資料與其他 page 26

Hamilton 黑白棋盤一筆畫摘要本研究一開始探討 * 黑白棋盤任一組黑白格作為起終點能否一筆畫完成並延伸探討各種不同關係棋盤能否對角線一筆畫完成, 且利用放障礙物的方法將不能對角線一筆畫完成之棋盤轉為可以對角線一筆畫完成最後探討以騎士遊歷走法完成邊長 4n+1 之方陣及邊長為 (4n+1)*(4m+1) 之矩形的對角線一筆畫壹研究動機有一次我們看到一本書叫沒有數字的數學,

Go 由黃格出發, 無論下一步走直的或橫的, 一定到白格, 所以他的路徑所經過的格子必為黃白交錯, 要將 64 格全部走完不重複, 最後一格必為白格 Mr.Go 若想拜訪住在黃格的 Mr.No 至少會空出一白格 ( 如圖 1) 但若將 Mr.No 搬家到其中一白格並改名為 Mr.Yes 就能完成這個任務! ( 如圖 2) 圖 1:Mr.Go 拜訪 Mr.No( 失敗 ) 圖 2:Mr.

3 Hamilton 黑白棋盤一筆畫摘要本研究一開始探討 * 黑白棋盤任一組黑白格作為起終點能否一筆畫完成並延伸探討各種不同關係棋盤能否對角線一筆畫完成, 且利用放障礙物的方法將不能對角線一筆畫完成之棋盤轉為可以對角線一筆畫完成最後探討以騎士遊歷走法完成邊長 4n+1 之方陣及邊長為 (4n+1)*(4m+1) 之矩形的對角線一筆畫壹研究動機有一次我們看到一本書叫沒有數字的數學, 其中有個問題讓我們十分感興趣 : 一 8*8 的棋盤上住著 Mr.Go 和他的朋友, 且 Mr.Go 住在右下角有一天,Mr.Go 想拜訪住在左上角的 Mr.No 若規定他只能走直的或橫的, 不能走斜的, 且必須經過棋盤上所有格子, 最後到達 Mr.No 的家哪一條路線能完成這個任務呢? 這個問題的答案是找不到的若將棋盤著色成白黃交錯, 如下圖. 則白黃格各有 32 格若 Mr.Go 由黃格出發, 無論下一步走直的或橫的, 一定到白格, 所以他的路徑所經過的格子必為黃白交錯, 要將 64 格全部走完不重複, 最後一格必為白格 Mr.Go 若想拜訪住在黃格的 Mr.No 至少會空出一白格 ( 如圖 1) 但若將 Mr.No 搬家到其中一白格並改名為 Mr.Yes 就能完成這個任務! ( 如圖 2) 圖 1:Mr.Go 拜訪 Mr.No( 失敗 ) 圖 2:Mr.Go 拜訪 Mr.Yes( 成功 ) 只要 Mr.Go 和他朋友各住在白黃格就能達成任務嗎? 若在中途設置障礙物, 能否成功拜訪 Mr.No( 以下稱為對角線一筆畫完成 ) 呢? 若將棋盤改成 * 或 * 呢? 這一連串的問題讓我們開始接下來的研究 ( 為方便研究, 以下改為黑白棋盤 ) 貳研究目的一探討 * 黑白棋盤任意一組黑白格作為起終點能否一筆畫完成二探討 * 黑白棋盤至少需放幾個障礙物, 才能對角線一筆畫完成, 並研究其走法三探討 * * 黑白棋盤能否對角線一筆畫完成四探討 * 黑白棋盤除了不放障礙物外, 再放幾個障礙物也能對角線一筆畫完成, 並研究其走法 - 1 -

4 Hamilton 黑白棋盤一筆畫五探討 * 黑白棋盤除了不放障礙物外, 再放幾個障礙物也能對角線一筆畫完成, 並研究其走法六由 * 黑白棋盤放一個障礙物延伸, 探討放三個障礙物的走法七延伸 ~ 黑白棋盤騎士遊歷對角線一筆畫參研究設備及器材黑白方格紙數張鉛筆 2 枝肆研究過程或方法一探討 * 黑白棋盤任意一組黑白格作為起終點能否一筆畫完成 1. 將黑白方格紙裁剪成 * 黑白棋盤 2. 用有系統的走法證明此棋盤任意一組黑白格作為起終點能否一筆畫完成 3. 整理所得的結果二探討 * 黑白棋盤至少需放幾個障礙物, 才能對角線一筆畫完成, 並研究其走法 1. 將黑白方格紙裁剪成 * 黑白棋盤 2. 用有系統的走法證明此棋盤至少需放幾個障礙物, 才能對角線一筆畫完成 3. 整理所得的結果三探討 * * 黑白棋盤能否對角線一筆畫完成 1. 將黑白方格紙裁剪成 * * 黑白棋盤 ( 如圖 3 4) 2. 用有系統的走法證明 * * 黑白棋盤能否對角線一筆畫完成 3. 整理所得的結果圖 3: * 黑白棋盤圖 4: * 黑白棋盤四探討 * 黑白棋盤除了不放障礙物外, 再放幾個障礙物也能對角線一筆畫完成, 並研究其走法 1. 將黑白方格紙裁剪成 * 黑白棋盤 2. 用有系統的走法證明此棋盤除了不放障礙物外, 再放幾個障礙物也能對角線一筆畫完成, 並研究其走法 - 2 -

3. 整理所得的結果 Hamilton 黑白棋盤一筆畫五探討 * 黑白棋盤除了不放障礙物外, 再放幾個障礙物也能對角線一筆畫完成, 並研究其走法 1. 將黑白方格紙裁剪成 * 黑白棋盤 2. 用有系統的走法證明此棋盤除了不放障礙物外, 再放幾個障礙物也能對角線一筆畫完成, 並研究其走法 3. 整理所得的結果六由 * 黑白棋盤放一個障礙物延伸, 探討放三個障礙物的走法 1.

5 3. 整理所得的結果 Hamilton 黑白棋盤一筆畫五探討 * 黑白棋盤除了不放障礙物外, 再放幾個障礙物也能對角線一筆畫完成, 並研究其走法 1. 將黑白方格紙裁剪成 * 黑白棋盤 2. 用有系統的走法證明此棋盤除了不放障礙物外, 再放幾個障礙物也能對角線一筆畫完成, 並研究其走法 3. 整理所得的結果六由 * 黑白棋盤放一個障礙物延伸, 探討放三個障礙物的走法 1. 將黑白方格紙裁剪成 * 黑白棋盤 2. 用有系統的走法證明此棋盤放三個障礙物, 能否對角線一筆畫完成, 並研究其走法 3. 整理所得的結果七延伸 ~ 黑白棋盤騎士遊歷對角線一筆畫 1. 將黑白方格紙裁剪成 4n+1*4n+1 黑白棋盤 2. 用有系統以騎士遊歷方法, 能否對角線一筆畫完成 3. 整理所得的結果伍研究結果一探討 * 黑白棋盤任意一組黑白格作為起終點能否一筆畫完成 1. * 棋盤不但能同邊角落進出完成一筆畫 ( 如圖 5), 也能對角線一筆畫完成 ( 如研究三 ) ; * 棋盤可從數邊角落進出完成一筆畫 ( 如圖 6), 也能對角線一筆畫完成 ( 如研究三 ); * 棋盤雖不能對角線一筆畫完成, 但可從同邊角落進出完成一筆畫 ( 如圖 7) 2. 解法 : 我們據上述原理, 利用作為起終點的白黑格作一矩形的對角線頂點, 並將矩形四邊向外延伸, 使此棋盤分為數個區塊, 據長寬的分布可歸納出十種不同可能圖 5: * 同邊角落進出圖 6: * 數邊角落進出圖 7: * 同邊角落進出 - 3 -

6 Hamilton 黑白棋盤一筆畫狀況一 ( 如右圖 ) (1). 據 * 棋盤原理, 可從 a( 起 ) 點走到 b 點 (2). 據 * 棋盤原理, 可從 b 點走到 c 點 (3). 據 * 棋盤原理, 可從 c 點走到 d 點 (4). 據 * 棋盤原理, 可從 d 點走到 e( 終 ) 點狀況二 ( 如右圖 ) (1). 據 * 棋盤原理, 可從 a( 起 ) 點走到 b 點 (2). 據 * 棋盤原理, 可從 b 點走到 c 點 (3). 據 * 棋盤原理, 可從 c 點走到 d 點 (4). 據 * 棋盤原理, 可從 d 點走到 e 點 (5). 據 * 棋盤原理, 可從 e 點走到 f( 終 ) 點狀況三 ( 如右圖 ) (1). 據 * 棋盤原理, 可從 a( 起 ) 點走到 b 點 (2). 據 * 棋盤原理, 可從 b 點走到 c 點 (3). 據 * 棋盤原理, 可從 c 點走到 d 點 (4). 據 * 棋盤原理, 可從 d 點走到 e( 終 ) 點狀況四 ( 如右圖 ) (1). 從 a( 起 ) 點走一直線到 b 點 (2). 據 * 棋盤原理, 可從 b 點走到 c 點 (3). 據 * 棋盤原理, 可從 c 點走到 d 點 (4). 據 * 棋盤原理, 可從 d 點走到 e 點 (5). 據 * 棋盤原理, 可從 e 點走到 f 點 (6). 據 * 棋盤原理, 可從 f 點走到 g( 終 ) 點 - 4 -

7 Hamilton 黑白棋盤一筆畫狀況五 ( 如右圖 ) (1). 據 * 棋盤原理, 可從 a( 起 ) 點走到 b 點 (2). 據 * 棋盤原理, 可從 b 點走到 c 點 (3). 據 * 棋盤原理, 可從 c 點走到 d( 終 ) 點狀況六 ( 如右圖 ) (1). 據 * 棋盤原理, 可從 a( 起 ) 點走到 b 點 (2). 據 * 棋盤原理, 可從 b 點走到 c 點 (3). 據 * 棋盤原理, 可從 c 點走到 d 點 (4). 據 * 棋盤原理, 可從 d 點走到 e( 終 ) 點狀況七 ( 如右圖 ) (1). 據 * 棋盤原理, 可從 a( 起 ) 點走到 b 點 (2). 據 * 棋盤原理, 可從 b 點走到 c 點 (3). 據 * 棋盤原理, 可從 c 點走到 d 點 (4). 據 * 棋盤原理, 可從 d 點走到 e( 終 ) 點狀況八 ( 如右圖 ) (1). 據 * 棋盤原理, 可從 a( 起 ) 點走到 b 點 (2). 據 * 棋盤原理, 可從 b 點走到 c 點 (3). 據 * 棋盤原理, 可從 c 點走到 d 點 (4). 據 * 棋盤原理, 可從 d 點走到 e( 終 ) 點 - 5 -

8 Hamilton 黑白棋盤一筆畫狀況九 ( 如右圖 ) (1). 據 * 棋盤原理, 可從 a( 起 ) 點走到 b 點 (2). 據 * 棋盤原理, 可從 b 點走到 c 點 (3). 據 * 棋盤原理, 可從 c 點走到 d( 終 ) 點狀況十 ( 如右圖 ) (1). 據 * 棋盤原理, 可從 a( 起 ) 點走到 b 點 (2). 據 * 棋盤原理, 可從 b 點走到 c 點 (3). 據 * 棋盤原理, 可從 c 點走到 d( 終 ) 點 3. 有些情況若沒有在上述狀況中出現, 則為上述情況翻轉九十度或翻面之情形 ( 以下研究皆有此種情況 ) 二探討 * 黑白棋盤至少需放幾個障礙物, 才能對角線一筆畫完成, 並研究其走法 1. 若 * 黑白棋盤白格進白格出, 則至少會空出一黑格故若放一障礙物於黑格, 則此棋盤應能對角線一筆畫完成 2. 解法 (1). 以障礙物為中心, 做出一個九宮格, 並將九宮格邊線延長, 分為九區 ( 第一區為左上, 第二區為中上, 第三區為右上, 依此類推 ) (2). 設右圖黃框長為數格, 且起點為白格, 終點為黑格 ; 因障礙物在黑格, 故黃框寬為數格第一區長為數格減二格亦為數格 ; 第一區寬為數格減二格亦為數格若黃框關係相反, 亦然 (3). 故黑白棋盤之關係如圖 ( ) 3 ( ) ( ) 3 ( ) - 6 -

9 狀況一 ( 如右圖 ) (1). 走完第一四七區, 會到第一區右上格 (2). 接著走第二三區, 走完會到第三區右下格 (3). 然後走第五六區, 沿著障礙物走一圈後, 繼續走第六區, 會到第六區右下格 (4). 最後走完第八九區, 到達終點狀況二 ( 如右圖 ) (1). 走完第一二三區, 因是 *, 故會走到第一區左下格 (2). 接著走完第四五六區, 因是 * 放一個障礙物, 故可從第四區左上角格走到第四區左下格 (3). 最後將第七八九區格子走完因是 *, 故可從第七區左上格走到終點 3 3 Hamilton 黑白棋盤一筆畫 3 3 狀況三 ( 如右圖 ) (1). 障礙物在邊上, 圍繞的九宮格會少一排, 高也會少一區 ( 第一區為左上, 第二區為中上, 第三區為右上, 依此類推 ) (2). 因障礙物必在黑格, 故第一區右上格必為黑格, 所以第一區有一邊為數格, 第三區有一邊為數格 ; 因 a 為 2 格, 故 b 為數格 (3). 走法 : 依序走完第一二三區, 會到第三區右下格 (4). 因第四五六區為 *, 故可由第六區右上格到達終點 2 3 a b - 7 -

10 狀況四 ( 如右圖 ) (1). 與情況三相似, 即情況三由右上角向左下角翻面 (2). 走法 : 走完一二區, 因第一二區為 *, 故可由起點走到第一區左下格 (3). 接著走第三區, 可由左上格走到左下格 (4). 然後走第五區, 因為 *, 故可從左上格走到右下格 (5). 最後走完第四六區, 因第四六區為 *, 故可從第六區左下格走到終點 3 2 Hamilton 黑白棋盤一筆畫三探討 * * 黑白棋盤能否對角線一筆畫完成 1. * 黑白棋盤 (1). 因 * 黑白棋盤有數排, 故必可從左上端到右下端 (2). 由此可知 * 黑白棋盤能對角線一筆畫完成 ( 如圖 8) 2. * 黑白棋盤 (1). 因 * 黑白棋盤有數排, 故必可從左上端到右下端 (2). 由此可知 * 黑白棋盤能對角線一筆畫完成 ( 如圖 9) 圖 8: * 黑白棋盤圖 9: * 黑白棋盤四探討 * 黑白棋盤除了不放障礙物外, 再放幾個障礙物也能對角線一筆畫完成, 並研究其走法 1. 因 * 黑白棋盤白黑格相差一格 ( 白格比黑格多一格 ), 且起終點皆為白格, 故能對角線一筆畫完成 2. 若放障礙物於白格, 則白黑格數一樣, 但起終點皆為白格, 故至少會空出一黑格 ( 如圖 10) 3. 若放障礙物於黑格, 則白格比黑格多二格, 但起終點皆為白格, 故至少會空出一白格 ( 如圖 11) 4. 若白黑格各放一個障礙物, 則白格比黑格多一格, 故此棋盤應能對角線一筆畫完成 ( 如下解法 ) - 8 -

11 Hamilton 黑白棋盤一筆畫圖 10: 放一障礙物於白格, 空一黑格圖 11: 放一障礙物於黑格, 空一白格 5. 解法 : 我們利用放障礙物的白黑格作一矩形的對角線頂點, 並將矩形四邊向外延伸, 使此棋盤分為數個區塊, 並由左到右, 由上到下編號 1~9 區, 據長寬的分布可歸納出七種不同可能狀況一 ( 如右圖 ) (1). 從起點出發, 由於第一四七區為 *, 故可從 a 走到 b (2). 接下來走第二區, 由於為 *, 故可走到 c (3). 接下來走完第五區後, 由於第六區為 *, 故可走到 e 點 (4). 最後走完第三六九區, 由於為 *, 故可走到終點, 即完成狀況二 ( 如右圖 ) (1). 先走完第一四七區, 由於為 *, 故可從 a 點走到 b 點 (2). 接下來走第八區, 因為是 *, 故可走到 c 點 (3). 接下來走第五區後, 走完第二區, 因為是 *, 故可走到 e 點 (4). 最後走完第三六九區, 因為是 *, 故可到達終點, 即完成 - 9 -

12 狀況三 ( 如右圖 ) (1). 先走完第一四區, 由於為 *, 故可從 a 走到 b (2). 接下來走第二五區最靠左的一行, 到達 c (3). 接下來將第二區走完後, 到達 d (4). 然後走完第五區剩下部分, 由於為 *, 故可走到 e (5). 最後走完第三六區, 因為是 *, 故可到達終點, 即完成 Hamilton 黑白棋盤一筆畫狀況四 ( 如右圖 ) (1). 先走完第一四區, 由於為 *, 故可從 a 走到 b (2). 接下來走第二五區最靠左的一行, 到達 c (3). 接下來先走完第二區最上方的兩排, 到達 d, 再走完第三區, 由於為 *, 可到達 e (4). 最後由 e 出發, 先走到第二區, 走完剩下格子後, 再將第五六區剩下格子走完, 即完成狀況五 ( 如右圖 ) (1). 先走完第一四區, 由於為 *, 故可從 a 走到 b (2). 接下來走第二五區最靠左的一行, 到達 c (3). 接下來走完第二區剩下格子, 可到達 d (4). 然後走完第五區剩下格子, 由於為 *, 故可到達 e (5). 最後走完第三六區, 因為是 *, 故可到達終點, 即完成

13 狀況六 ( 如右圖 ) (1). 先走完第一四區, 由於為 *, 故可從 a 走到 b (2). 接下來走第二五區最靠左的一行, 到達 c (3). 接下來由 c 點出發, 走到下方障礙物上面一排的最右格, 由於為白格進, 黑格出, 故可到達 d 點 (4). 然後走完二三區剩下的格子, 到達 f (5). 最後走完第五六區剩下格子, 到達終點, 即完成狀況七 ( 如右圖 ) (1). 先走完第一四區, 由於為 *, 故可從 a 走到 b (2). 接下來走第二五區最靠左的一行, 到達 c (3). 接下來走完第二區剩下格子, 可到達 d (4). 最後走完第四區剩下格子, 由於為黑格進, 白格出, 故可到達終點, 即完成 Hamilton 黑白棋盤一筆畫五探討 * 黑白棋盤除了不放障礙物外, 再放幾個障礙物也能對角線一筆畫完成, 並研究其走法 1. 因 * 黑白棋盤白黑格數一樣, 且起點為白格終點為黑格, 故能對角線一筆畫完成 2. 若放一障礙物於白格, 則白黑格相差一格 ( 黑格比白格多一格 ), 但起點為白格, 終點為黑格, 故至少會空出一黑格 ( 如圖 12) 3. 若放一障礙物於黑格, 則白黑格相差一格 ( 白格比黑格多一格 ), 但起點為白格, 終點為黑格, 故至少會空出一白格 ( 如圖 13) 4. 若在白黑格各放一個障礙物, 則白黑格數一樣, 故此棋盤應能對角線一筆畫完成 ( 如下解法 ) 圖 12: 放一障礙物於白格, 空一黑格圖 13: 放一障礙物於黑格, 空一白格

14 Hamilton 黑白棋盤一筆畫 5. 解法 : 我們利用放障礙物的白黑格作一矩形的對角線頂點, 並將矩形四邊向外延伸, 使此棋盤分為數個區塊, 並由上而下, 由左而右編號 1~9 區, 據長寬的分布可歸納出十五種不同可能狀況一 ( 如右圖 ) (1). 先走完第一四區, 因為是 *, 故可由 a 走到 b (2). 接下來走第二五區, 最後會到達 c 點 (3). 接下來走第三六區, 由於為 *, 故可到達 d 點 (4). 最後走完第七八九區, 由於為 *, 故可走到終點, 即完成狀況二 ( 如右圖 ) (1). 先走完第一二三區, 由於為 *, 故可從 a 走到 b (2). 接下來走第四七區, 由於為 *, 故可走到 c (3). 接下來走完第五八區, 到達 d (4). 最後走完第六九區, 因為是 *, 故可到達終點, 即完成

15 狀況三 ( 如右圖 ) (1). 先走第一四七區, 由於為 *, 故可從 a 走到 b (2). 接下來走第二三區, 由於為 *, 故可走到 c (3). 接下來走第五六區, 可到達 d (4). 然後走第八區, 由於為白格進黑格出, 故可到達 e (5). 最後走完第九區, 因為是 *, 故可走到終點, 即完成 Hamilton 黑白棋盤一筆畫狀況四 ( 如右圖 ) (1). 先走完第一四七區, 由於為 *, 故可從 a 走到 b (2). 接下來走第二三區, 由於為 *, 故可走到 c 點 (3). 接下來走第五六區, 可到達 d (4). 最後走完第八九區, 因為是 *, 故可到達終點, 即完成第五種可能 ( 如右圖 ) (1). 先走第一四七區, 由於是 *, 故可由 a 走至 b (2). 接下來走第二區, 由於為 *, 故可到達 c (3). 接下來走第三六區, 由於為 *, 故可走到 d (4). 先向下走一排後, 進入第五區, 走完後會到達 e (5). 最後走完第八九區剩下的格子, 到達終點, 即完成

16 狀況六 ( 如右圖 ) (1). 先走第一二三區, 由於為 *, 故可由 a 到達 b (2). 接下來走第四七區, 由於為 *, 故可到達 c (3). 接下來走第五八區最靠左的一行, 到達 d (4). 然後走完第五六區, 過程中須繞過障礙物, 最後到達 e (5). 最後再將第八九區剩下格子走完, 由於為黑格進, 白格出, 故最後會到達終點, 即完成 Hamilton 黑白棋盤一筆畫狀況七 ( 如右圖 ) (1). 先走完第一四區, 由於為 *, 故可從 a 走到 b (2). 接下來走第二五區最靠左的一行, 到達 c (3). 接下來走第二區剩下格子, 到達 d 後, 在走完第五區剩下格子, 由於為 *, 故最終到達 e (4). 最後走完第三六區, 由於為 *, 故可到達終點, 即完成狀況八 ( 如右圖 ) (1). 先走完第一四區, 由於為 *, 故可從 a 走到 b (2). 接下來走第二五區最靠左的一行, 到達 c (3). 接下來走第二區剩下格子, 到達 d 後, 在走完第五區剩下格子, 由於為 *, 故最終到達 e (4). 最後走完第三六區, 由於為 *, 故可到達終點, 即完成

17 狀況九 ( 如右圖 ) (1). 先走完第一四區, 由於為 *, 故可從 a 走到 b (2). 接下來走第二五區最靠左的一行, 到達 c (3). 然後走完第二三區, 過程中須繞過障礙物, 最後到達 f (4). 接下來走第五區, 由於為 *, 故可到達 g (5). 最後將第六區剩下格子走完, 因為是黑格進黑格出, 但已走完一白格, 故可到達終點, 即完成 Hamilton 黑白棋盤一筆畫狀況十 ( 如右圖 ) (1). 先走完第一四區, 由於為 *, 故可從 a 走到 b (2). 接下來走第五區, 由於為 *, 故可到達 c (3). 接下來走完第二區, 最後會到達 d (4). 最後走完第三六區, 由於為白格進黑格出, 故可到達終點, 即完成狀況十一 ( 如右圖 ) (1). 先走第一二區, 由於為 *, 故可由 a 至 b (2). 接下來走第四區, 由於為 *, 故可到達 c (3). 先向下走一排後, 再向上走完第三區, 最後到達 d (4). 然後走完第五區剩下格子, 由於為黑進格進白格出刪去一黑格一白格, 故會到達 e (5). 最後走完第六區剩下格子, 由於為 *, 故最後會到達終點, 即完成

18 狀況十二 ( 如右圖 ) (1). 先走第一二區, 由於為 *, 故可由 a 至 b (2). 接下來走第四區, 由於為 *, 故可到達 c (3). 接下來走完第三區, 最後到達 d (4). 然後走完第五區, 由於為白格進黑格出, 故會到達 e (5). 最後走完第六區, 由於為 *, 最後會到達終點, 即完成 Hamilton 黑白棋盤一筆畫狀況十三 ( 如右圖 ) (1). 先走完第一區, 由於為 *, 故可由 a 走至 b (2). 接下來走第二四區, 由於為 *, 故會到達 c (3). 接下來先向下走一排, 到達 d, 再向上走完第三區, 最後到達 e (4). 然後走完第五區剩下格子, 由於為白進格進黑格出刪去一黑格一白格, 故會到達 f (5). 最後走完第六區剩下格子, 由於為 *, 故最後會到達終點, 即完成狀況十四 ( 如右圖 ) (1). 先走完第一三區, 由於為 *, 故可從 a 走到 b (2). 接下來走第二四區最靠左的一行, 到達 c (3). 接下來走完第二區剩下格子, 最後到達 d (4). 最後走完第四區剩下格子, 由於為白格進黑格出, 故可到達終點, 即完成

19 狀況十五 ( 如右圖 ) (1). 先走完第一三區, 由於為 *, 故可從 a 走到 b (2). 接下來走第二四區最靠左的一行, 到達 c (3). 接下來走完第二區剩下格子, 最後到達 d (4). 最後走完第四區剩下格子, 由於為 *, 故可到達終點, 即完成 Hamilton 黑白棋盤一筆畫六由 * 黑白棋盤放一個障礙物延伸, 探討放三個障礙物的走法 1. 因 * 黑白棋盤放障礙物於黑格可對角線一筆畫完成, 若 * 黑白棋盤放三個障礙物於 2 黑 1 白, 因與放一個障礙物一樣, 會多放一黑格, 故應可對角線一筆畫完成 2. 因 * 黑白棋盤放三個障礙物可能情況太多, 故我們只研究出較簡易走法分隔線為直的如右圖, 將在白黑格的障礙物各一格分為一區, 另一在黑格的障礙物分為一區 ( 即右圖綠線 ) 將 * 黑白棋盤分為兩個 * 的矩形因 * 黑白棋盤放兩個障礙物可由 a 點走到 b 點, 放一個障礙物則可從 c 點走到 d 點加一排

20 Hamilton 黑白棋盤一筆畫若障礙物橫的並排於邊上則將棋盤分成數塊走法 : 橫 (1). 先走完第一二區, 因為為 *, 故可由 a 走至 b 的並 (2). 接下來走第四區, 由於為 *, 故可排走至 c (3). 接下來走完第三區, 若不看障礙物, 為 *, 故可到達 d (4). 最後走第五六區, 因為是 *, 故可到達終點, 即完成若障礙物直的並排於邊上則將棋盤分成數塊走法 : 直 (1). 先走第一三區, 由於為 *, 故最後會到達 (2). 接下來走第二區, 由於為 *, 故會的並排到達 c (3). 最後走完第四區, 若不看障礙物, 為 *, 故可到達終點, 即完成七. 黑白棋盤騎士遊歷對角線一筆畫前言 : 一隻馬能否跳遍空棋盤上的每一個交叉點? 答案是肯定的, 稍具象棋知識的人, 都能準確回答這個問題但是若進一步要求 : 是否能找到一條路徑, 讓馬跳遍空棋盤上所有交叉點的過程中, 任意一個交叉點只允許被馬踩過一次? 後面這個問題, 恐怕要難倒許多人了這個古老難題, 在西方稱之為騎士旅遊 (Knight's Tour), 早在十六世紀時, 瑞士數學家貝爾特蘭德 (Bertrand) 即提出這個問題而我們將原本的問題, 改為以相同走法做對角線一筆畫 1. 在 * 黑白棋盤中, 因為與前文之走法 ( 走相鄰之格子 ) 相似 ( 同為由黑格走至白格, 再由白格走至黑格 ) 因 * * 黑白棋盤白黑格相差一格 ( 白格比黑格多一格 ), 且起終點皆為白格, 故能對角線一筆畫完成, 但在 * 黑白棋盤中白黑格相同, 且起終點皆為白格, 故無法對角線一筆畫完成, 所以不討論 * 方陣經過我們反覆研究後, 發現以 4n+1 為邊長之矩形或方陣較有規律, 故這裡只討論 4n+1 矩形及方陣

21 Hamilton 黑白棋盤一筆畫 4n+1 方陣使用點對稱原因 : 因為一開始, 我們並未鎖定 * 方陣進行研究, 我們一開始發現到 : 任意一種 * 或 * 的圖形, 以順時針或逆時針方式, 沿著外圍繞, 以這種方式成功的機率蠻高的, 但始終無法發現有什麼規律直到某一次試了 5*5 圖形, 我們走完半圈後, 剛剛好填數字部分與空白部分呈現點對稱的圖形 ( 如左圖 ) 所以我們突發想, 是否能以起點終點分別當作兩端起點, 兩邊路徑都遵循著點對稱的方式, 來完成這個方陣呢? 經過我們反覆嘗試後, 得到上述結果 3. 走法如右圖為 5*5 方陣, 同時由 1 25 為出發點, 以騎士遊歷方式, 13 為對稱點, 以點對稱方式 ( 如由 1 走到 2, 另一端則由 25 走到 24) 依序先走完外圍 2 圈, 走完外圍最後所到的點 (12 14 處 ), 必能走到中間, 即完成外圍部分解釋如右圖, 我們將以 1 為起點的路徑標示為藍色, 以 25 為起點的路徑標示為灰色, 順著藍色路徑走 ( 沿著邊走 ), 恰能到達 12( 即起點下方 ) 在每個 4n+1 為邊長的正方形中, 都可以到達此點, 之後皆能從此點走至內部 ( 即右圖 13) 內部方陣邊長必為原方陣之邊長 4, 故可以再走至終點上方 ( 即右圖 14)14 12 互為以 13 為對稱點之點對稱, 所以可以再依照點對稱方式, 必可到達終點, 且兩路徑恰好能填完外圍兩圈, 各占一半格數

22 Hamilton 黑白棋盤一筆畫右圖同為一邊長為 4n+1 之方陣 (9*9), 因為 5 與 9 邊長差 4, 我們發現到, 與 5*5 方陣類似, 都可以從起點走至右上角這一點 ( 即圓圈處,5*5 方陣中圓圈處為 3), 之後又能從此點再走至終點左方三格的位置, 所以走外圈的情形會與 5*5 類似, 都能走到起點下方, 走進內部後, 又是一個 5*5 方陣, 所以一定能到此 5*5 方陣之終點 ( 即右圖 53), 再走至終點上方 ( 即右圖 54)54 28 互為以 41 為對稱點之點對稱, 所以可以再依照點對稱方式, 必可到達終點 9*9 矩形圖解如左圖,13*13 方陣可以用同樣方式走完外圍, 而內圈又是一 9*9 方陣, 也可以用同樣方式走完外圈後, 內圈又是 5*5 方陣, 故一定能完成 *13 矩形圖解

23 Hamilton 黑白棋盤一筆畫 5. 結論 4n+1 方陣外圍兩路徑恰好能填完外圍兩圈, 各占一半格數, 且最後會到達起點下方及終點上方, 此點必能走至內圈, 而內圈這一個方陣邊長為原方陣減 4, 再依據同樣方法, 最後一定能完成這一個方陣 (4n+1)*(4m+1) 矩形 6. 我們將 5*(4m+1) 的矩形定為基本型, 其他 (4n+1)*(4m+1) 只要像 4n+1 的方陣一樣走完外圍最後剩 5*(4n+1) 時, 照基本型的走法走完即可 ( 如 13*21 走完外圍剩 9*17,9*17 走完外圍剩 5*13, 再照基本型的走法走完 ) 7. 走法把 1 45 同時作為起點, 順時針繞外圍兩排並設法走到起點下或上方 ( ) 接著反方向繞外圍兩排, 並盡量以下中上中下的規律走到起點的右下或左下方 ( ) 最後會只剩一條直達終點的路 ( ), 只要跟著他走完即完成 ( ) 因上已經走過, 故只能往下下中上中下 7. 舉例 *9 矩形走法因上已經走過, 故只能往下走

Hamilton 黑白棋盤一筆畫 1 58 75 38 3 60 73 34 5 44 71 46 7 64 69 30 9 20 37 2 59 74 35 4 61 72 33 6 63 70 31 8 65 68 57 76 19 36 39 54 41 24 43 62 45 32 47 50 67 10 29 18 21 78 55 16 23 80 53 14 25 82 51 12

24 Hamilton 黑白棋盤一筆畫 *17 矩形走法 5*17 矩形走法因上已經走過, 故只能往下走陸討論一. * * 棋盤不能放障礙物的格子我們發現右圖或不能放置障礙物 ( 但若第二個障礙物放在或則可 ) 若放置障礙物於或任意一格, 進入或其中一格時則不能再走出去, 故不能對角線一筆畫完成

25 Hamilton 黑白棋盤一筆畫二 * 黑白棋盤不能放障礙物的格子及組合 1. 像圖 14 的橘格, 若障礙物放在橘格上, 只要進去就無法出來 ( 若要出去就會一格走兩遍 ), 但若在橘框周圍位置 ( 即圖 14 橘框周圍之綠框 ), 其中一格放障礙物則不會形成一格走兩次的情形 ( 如圖 15 理由 ) 2. 若障礙物以特定方式排列, 也會形成死路如 :(1). 在邊上的任一黑格與這黑格的斜對角 ( 如圖 16 橘線圖 17 理由 ) (2). 在邊上兩黑格只間格一白格 ( 如圖 18 相同顏色圓點圖 19 理由 ) 三. 綜合以上, 若依各種黑白棋盤放三個障礙物不出現無解的前提 : 1. 放障礙物的格子不能出現在無解格內, 除非將障礙物放於可使無解變有解的格子 2. 棋盤邊長盡量長, 無解格就佔的較少 3. 障礙物不要放太密, 易導致無解一次走完走第二次圖 14: 不能刪的格子舉例 ~1 圖 15: 不能刪的格子理由走第二次圖 16: 不能刪的格子組合舉例 ~2 圖 17: 不能刪的格子理由

Hamilton 黑白棋盤一筆畫走第二次圖 18: 不能刪的格子組合舉例 ~3 圖 19: 不能刪的格子理由柒結論一因 * 黑白棋盤只能白格進白格出, 但白黑格數一樣, 故至少會空出一黑格, 故無法對角線一筆畫, 又因 * * 黑白棋盤有數排, 故能對角線一筆畫完成二若 * 黑白棋盤任意一組黑白格作為起終點, 以分割方式及各區域之關係證明能一筆畫完成三若 * 黑白棋盤起

26 Hamilton 黑白棋盤一筆畫走第二次圖 18: 不能刪的格子組合舉例 ~3 圖 19: 不能刪的格子理由柒結論一因 * 黑白棋盤只能白格進白格出, 但白黑格數一樣, 故至少會空出一黑格, 故無法對角線一筆畫, 又因 * * 黑白棋盤有數排, 故能對角線一筆畫完成二若 * 黑白棋盤任意一組黑白格作為起終點, 以分割方式及各區域之關係證明能一筆畫完成三若 * 黑白棋盤起終點皆為白格, 刪去一黑格, 則白格比黑格多一格, 以分割方式及各區域之關係證明能對角線一筆畫完成四若 * 黑白棋盤起終點皆為白格, 刪去白黑各一格, 則白格比黑格多一格, 以分割方式及各區域之關係證明能對角線一筆畫完成五若 * 黑白棋盤起點為白格終點為黑格, 刪去白黑各一格, 則白黑格數一樣, 以分割方式及各區域之關係證明能對角線一筆畫完成六若 * 黑白棋盤起終點皆為白格, 刪去一白格二黑格, 則白格比黑格多一格, 以分割方式及各區域之關係證明能對角線一筆畫完成七在對角線騎士遊歷一筆畫中, 因 * * 黑白棋盤白黑格相差一格 ( 白格比黑格多一格 ), 且起終點皆為白格, 故能對角線一筆畫完成, 但在 * 黑白棋盤中白黑格相同, 且起終點皆為白格, 故無法對角線一筆畫完成, 並發現每一個邊長為 4n+1 之方陣具有下述特性 : 恰好能填完外圍兩圈, 且最後會到達起點下方及終點上方, 此兩點必能走至內圈, 而內圈這一個方陣邊長為原方陣減 4, 再依據同樣方法, 最後一定能完成這一個方陣八在 (4n+1)*(4m+1) 矩形中, 依照我們所設計之走法必能對角線騎士遊歷一筆畫完成捌未來的展望一將對角線黑白棋盤一筆畫由平面改為立體, 並研究其規律

27 Hamilton 黑白棋盤一筆畫二在對角線騎士遊歷中, 我們只發現邊長 4n+1 之方陣及邊長為 (4n+1)*(4m+1) 之矩形有規律並找出解法, 希望未來能更深入研究邊長 4n+3 之方陣邊長為 (4n+3)*(4m+3) 之矩形及 * 圖形之規律及解法玖參考資料及其他一路障圖片取自二徐力行 (2003): 沒有數字的數學天下遠見出版社三中華民國象棋文化協會象棋專欄 : 棋盤上的數學遊戲 - 騎士旅遊 (Knight's Tour) 感謝參閱敬請指教

0 0 = 1 0 = 0 1 = = 1 1 = 0 0 = 1

0 0 = 1 0 = 0 1 = = 1 1 = 0 0 = 1 0 0 = 1 0 = 0 1 = 0 1 1 = 1 1 = 0 0 = 1 : = {0, 1} : 3 (,, ) = + (,, ) = + + (, ) = + (,,, ) = ( + )( + ) + ( + )( + ) + = + = = + + = + = ( + ) + = + ( + ) () = () ( + ) = + + = ( + )( + ) + = = + 0

目錄 摘要 page 2 研究動機 page 2 研究目的 page 2 研究設備與器材 page 3 研究過程與方法 page 3 研究結果研究一 page 4 研究二 page 7 研究三 page 9 研究四 page 9 研究五 page 12 研究六 page 18 研究七 page 19

目錄摘要 page 2 研究動機 page 2 研究目的 page 2 研究設備與器材 page 3 研究過程與方法 page 3 研究結果研究一 page 4 研究二 page 7 研究三 page 9 研究四 page 9 研究五 page 12 研究六 page 18 研究七 page 19