最長迴路

出自　創作パズルVI　方陣の最長回路  朝井 幸洋
而那篇文章是參考 Martin Gardner 的文章，目前還沒找到Martin Gardner 的那篇文章
---

這個puzzle可以分成兩個部分。
第一個部分可以作為學生熟悉長度概念、練習加法的問題，並討論奇偶數的性質。
第二個部分可以給高年級學生玩，並用來向學生介紹一些圖論的分析問題技巧。學生可以嘗試去找出並證明甚麼狀況下會是最長迴路。

---
第一部分 直線版本

在下方數列上，填上1~9的數字。


如:

接著測量從1->2的距離、從2->3的距離、從3->4的距離、...、從8->9的距離、從9->1的距離
將距離全部加起來，計算總路徑長

這是不是最長的路徑？

可以讓 3年級的學生嘗試14個位置填1~14。練習100以下的加法。
討論與觀察 1~3、1~4、1~5、...、1~8 最長迴路的情形，藉此探討奇偶數的性質。




第二部分 方陣版本

4*4 方陣

同樣的方式，依1->2、2->3...的方式移動

如圖下

可以用數字與箭頭來表示，先從右上向下一格，再向左3格....


這樣的狀況下，要通過全部的點，最後回到原位，形成一個迴路。
什麼樣的迴路的路徑長度最長？

下圖是Gardner 提出的一個最長路徑 =38

下面介紹用不同的方式來看帶這個路徑

用箭頭圖表示:
所有數字加總 =38

將路徑標示出來

計算每個位置有幾條線通過的話，可以得到另一個圖形


將上圖全部數字除以2，所有數字加總 =38

計算每條邊通過幾條線，可以得到另一個圖形:
同樣的，所有數字加總 =38


上面都算解圖論問題，可能會用到的技巧。
視情況介紹這些技巧，讓學生思考能不能利用上面那些方式，來幫助探討找出最長迴路？
或者是否還能用甚麼不同的角度來看待這個問題？



最後可以讓學生思考 長方形 著色 的問題，要如何證明作為有興趣學生的課後練習。



最後方上另外兩種4*4的最長迴路 和 直線3、4、6的一些最長迴路
(不建議一開始就給學生看)

相關遊戲: Tricky Circles



----
//2016/11/3補充  出自Mathematical Puzzles by Stephen Ainley
n是奇數時，通常可以做出總長為 1+n(2*n^2 - 5)/3 的路徑 (不確定是不是最大)
n是偶數時，通常可以做出總長為 2+n(2*n^2 - 5)/3 的路徑

另外可以探討另一種變化型
n*n的方格中，填上1~n^2的數字，數字可以任意填，計算從1依序走道n^2再走回1所需的總長度，移動方式是上下左右移動(不走斜線)。如下圖1走到2的長度是3，下圖的總長度是
3+2+2+3+4+2+3+1+2 = 22

這樣的方式n*n的總長最多為多少？ 有多少總解？

變化型的問題實際上比原本的問題容易，
可以證明當n是奇數時最長路徑是(n^3-n)，n是偶數時最長路徑是(n^3-2)。
有多少解的問題應該也是國高中生可以探討的問題。