◆東京都 明 さんからの解答
【問題１】
２→９→14→22→31→24→19→11→４→７→21 →30→29→26→12→３→10→１→８→20→27 →32→25→28→16→５→17→13→６→18→23 →15 ２→９→14→22→31→24→19→11→４→15→27 →32→25→13→６→１→８→20→16→５→12 →３→10→18→23→30→29→26→17→28→21 →７ ２→９→14→22→31→24→19→11→16→７→４ →３→12→26→29→30→21→28→25→13→17 →５→８→20→27→32→23→18→６→１→10 →15 ２→９→14→22→31→24→19→11→16→５→17 →28→25→13→６→１→８→20→27→32→23 →30→21→７→４→３→12→26→29→18→10 →15【おまけ１】
巡回ルートは存在しません。
理由
この配列では２→９→14→22→31→24→19→11という特異なルートがあり、2,14,31,19 は、接続するマス目が２つしかないという特徴があります。
14を例にとると、この出入り口となる、9または22にナイトが来たとき、次に14以外のマス目にナイトを移動させると、14へ接続するマス目は１つとなり、14は終着点とならなくてはいけません。
したがって、2をスタートとして巡回路を作ろうとすればナイトは
２→９→14→22→31→24→19→11、
もしくは２→11→19→24→31→22→14→９と動くしかありません。
この両ルートとも 他のマス目を残して巡回路の終点となるべきマス目に戻ってしまいます。
したがって、巡回ルートは存在できません。
【おまけ２】
9,22,24,11を出発点とするとナイトはすべてのマスを通れません。
理由
出発点を9とすると、【おまけ１】と同じ理由で、2または14が終点となります。
9から、2と12以外のマス目に移動すると終点が２つとなるのでツアーが完成しません。
仮に14へナイトを移動させてツアーを完成できたとすると、2が終点になることになります。
これは2からスタートすれば巡回路ができることになり、【おまけ１】に矛盾します。
図形の対称性から22,24,11を出発点にしても同様にツアーは完成しません。
任意のマス目から出発して、すべてのマス目を通ることができる場合は、巡回路ができることを一般的に言えそうな気がしたのですが、Ｗｅｂでハミルトンパスを検索しましたら反例がでていました。
petersonグラフと言うそうです。
◆京都府の高校生 Positron さんからの解答
【問題１】
２→９→14→22→31→24→19→11→４→７→21 →30→29→26→12→３→10→15→23→18→６ →１→８→20→27→32→25→13→17→５→16 →28解法
グループＡ：2,9,14,22,31,24,19,11 グループＢ：4,7,21,30,29,26,12,3 グループＣ：10,15,23,18 グループＤ：6,1,8,20,27,32,25,13 グループＥ：17,5,16,28と５つに分け、Aを最初にしてＡに属する数字を全て通り、あとはB,C,D,Eを上手く行くように並びかえるだけで楽に見つけられる。
【おまけ１】
答え：できない
理由：
２から出発して、次に動けるのは９か１１のどちらか。
左右対称より、９に行っても、１１に行っても対称にすれば同じなので、９から行くとする。
すると２へ戻る一つ手前のマスは１１のみになる。
１９を通るルートについても同じ事が言え、１１→１９→２４か２４→１９→１１のどちらかになり、１１→２にするためには、２４→１９→１１→２となるルートしか存在しない。
同様に１４，３１についても同じこと
（２２→１４→２４か２４→１４→２２で、２４→１９→（略）から２２→１４→２４→（略））
が言えるから、２から出発して、２へ戻るには、グループＡの数字のみを通るか、１４，１９，２４のどれか一つ以上を通らないかのどちらかになる。
【おまけ２】
答え：９，２２，２４，１１
考え方：
おまけ１同様、９から始めると、２か１４は共に、前後に９を通る必要があるから、２→９→１４か１４→９→２の２通りが、ルート内に存在しなければならないが、９から始めるため、存在しない。
よって、この盤は左右対称、点対称でもありから、２２，２４、１１についても同様のことが言える。
◆千葉県の高校生 ガウチ さんからの解答
【問題１】
２→11→19→24→31→22→14→９→６→13→25 →32→27→20→８→１→10→３→12→26→17 →５→16→28→21→７→４→15→23→18→29 →30【おまけ１】
巡回ルートが存在すると仮定する。
左右対称であるから１手目で９に行くと、一般性を失わずに仮定する事ができる。
このとき最後に２に戻る為にはほかのすべてのマスを通った後、１１→２と行くしかない。
ここで１９について考えると、１１、２４の二つから行く事が考えられるが、１１はほかのすべてのマスを通った後に行かなければならないので、最後に２４→１９→１１→２と移動する事になる。
３１、１４についても同様の考察をすると、
２→９→１４→２２→３１→２４→１９→１１→２
と移動するしかない事がわかる。
しかし、これはすべてのマスを通っていないので矛盾。
よって巡回ルートが存在しない事が示された。
【おまけ２】
９、１１、２２、２４から出発するとすべてのマスを通れない事を示す。
対称性より出発点を１１であると、一般性を失わずに仮定できる。
１１から出発してすべてのマスを通るルートが存在すると仮定する。
ここで２について考えると最後に９→２と移動するしかない。
１４、３１、１９について同様の考察をすると、
１１→１９→２４→３１→２２→１４→９→２
と移動するしかない事がわかる。
しかしそうするとすべてのマスを通る事ができないので矛盾。
よって９、１１、２２、２４から出発してすべてのマスを通る事ができない事が示された。
【感想】
おまけ２は、ほかのマスについてはわからなかったのですが、問題文では「〜出発点はあるか？」とだけ聞いているので「ある」と答える事ができます。
あと、ナイトといえば次の問題を思い出しました。
８×８のマス目のある盤がある。ナイトが左上隅のマスからすべてのマスを通って最後に右下隅のマスに行く事は可能か？
◆広島県 清川 育男 さんからの解答
【問題１】
２→９→14→22→31→24→19→11→４→３→10 →１→６→13→17→26→12→５→８→20→16 →７→21→28→25→32→27→15→23→18→29 →30
左右対称なので、
11262*2=22524
２２５２４通り。
NO. 1 9→ 14→ 22→ 31→ 24→ 19→ 11→ 4→ 3→ 10→ 1→ 6→ 13→ 17→ 26→ 12→ 5→ 8→ 20→ 16→ 7→ 21→ 28→ 25→ 32→ 27→ 15→ 23→ 18→ 29→ 30→ NO. 2 9→ 14→ 22→ 31→ 24→ 19→ 11→ 4→ 3→ 10→ 1→ 6→ 13→ 17→ 26→ 12→ 5→ 8→ 20→ 16→ 7→ 21→ 28→ 25→ 32→ 27→ 15→ 23→ 30→ 29→ 18→ NO. 3 9→ 14→ 22→ 31→ 24→ 19→ 11→ 4→ 3→ 10→ 1→ 6→ 13→ 17→ 26→ 12→ 5→ 8→ 20→ 16→ 7→ 21→ 30→ 29→ 18→ 23→ 15→ 27→ 32→ 25→ 28→以下略。全リストはこちらです。(lzh圧縮)
【おまけ２】
４ ６ ８ ９ １０ １１ １２ １６ １７ ２１ ２２ ２３ ２４ ２５ ２７ ２９以上は出発点になれない。
【おまけ１】
存在しないことをプログラムで確認しました。
◆愛知県 Y.M.Ojisan さんからの解答
【問題１】
下図に示す。
【おまけ１】
巡回ルートは存在しない。
∵ ２，１４，１９，２１を通過する道筋は下図のように１通りしかない。
さらに、巡回ルートであるためには９，１１，２２，２４もまた通過しなければならず、
結局下図に示す四芒星が閉じてしまい、全体を通過できない。
【おまけ２】
全てのマスを通るようにナイトを動かすことのできない出発点はある。
下図の×がそれである。
∵おまけ１に示したように、２，１４，１９，２１は通過点にはなりえない。
従って、始点（＝終点）はその何れかである。
一般性を失わず２から出発し、かつ等価な１４，１９，２１は通過点としたとき、
９，１１，２２，２４は四芒星の一部として最初に通過しなければならず、終点とはなりえない。
つまり×である。
またチェッカボード状に塗り分け（黄色と緑）たとき、２を黄色とすると、終点は緑でなければならない。なぜなら黄色と緑の数は等しくかつ一回の移動ごとに必ず色が変わるからである。つまり ２，１４，１９，２１を除く黄色のところは終点（＝始点）にはなりえず×である。
なお、残ったところが終点（＝始点）になり○であることは、問題１において実証されている。
◆ 問題へもどる
◆ 今週の問題へ
数学の部屋へもどる