当サイトで扱う最初のテーマですが、数学が苦手な方にも興味を持っていただけるよう、数学パズルの一つである「ナイトツアー」について書いていきます。
ナイトツアーについて
ナイトツアーとは、「チェス盤上でナイトの駒を動かし、すべてのマス目をたった一度だけ通過することができるのか」という問題になります。
ナイトはチェスの中でも特殊な動きをする駒で、「今いるマス目から上下左右に２マス、そこから垂直方向どちらかに１マス」移動することができます。
将棋でいう桂馬と同じ動きに似ていて、桂馬は前方方向に２マス進む動き方しかできないのに対し、ナイトは前後左右のすべての方向に動くことができます。
一般的なチェス盤は８マス×８マスになっています。
結論から言ってしまえば、８×８のマス目に関してはナイトツアーを完成されることができます。下の例はその一例になっていて、数字を順番にたどっていくことですべてのマス目をたった一度だけ通ることができます。
これ以外にもナイトツアーが完成するような順路は数多く存在しています。
自分の手で他のルートを探してみるのも楽しいと思いますよ！
一番最後にスタートした位置に戻ってこれる？
ひとまず、８×８のマス目に関してはナイトツアーを完成させることができることがわかりました。
では、８×８のチェス盤の上で、最後に出発地点に戻れるようにすべてのマス目をたった一度だけ通るような順路は存在するでしょうか。
実はこのような順路は存在しません。
考えると意外と簡単で、チェス盤の上を動くナイトは ⋯ →白→黒→白→黒→⋯ といったように、白と黒のマス目を交互に移動していきます。
そして、最後に出発地点に戻るとすると最初のマス目から64回移動して最初のマス目に戻ってくるということですから、出発地点が白とすると、64回移動した後のマス目は必ず黒になります。出発地点のマス目の色を変えることはできませんから、このような順路は存在しないということになります。
他のサイズのマス目ではどうなるか
ここまでは実際のチェス盤に則って８×８のマス目でのナイトツアーを考えてきました。
では、他のサイズのマス目ではどうなるでしょうか。
下の例は５×５のマス目でのナイトツアーになっています。
このように、５×５のマス目においてもナイトツアーを完成させることができました。
ここで直感的に分かる方もいらっしゃると思いますが、５×５以上のマス目についてはナイトツアーを完成させることができます。証明は長くなるので省略させてください。（いずれ書くかも）
では、さらに小さいマス目ではどうなるでしょう？
まずは、３×３のマス目についてですが、真ん中のマス目と行き来できるマス目が存在していないため、ナイトツアーの条件である、「すべてのマス目を通過する」ことを満たすことができません。
つまり、３×３のマス目についてはナイトツアーを完成させるような順路は存在しないということがわかりました。
２×２のマス目についても同様で、すべてのマス目についてナイトの動きでは移動することができないので、２×２のマス目についてもナイトツアーを完成させるような順路は存在しないことがわかります。
５×５のマス目では出来て、３×３のマス目では出来ない、じゃあ４×４はどうなの？ということになります。
結論を言ってしまうと、４×４のマス目でもナイトツアーを完成させる順路は存在しません。
証明は長くなってしまうので割愛させていただきます。
簡単に、私が考えた証明の概要だけ説明しておこうと思います。少し分かりづらいかもしれないので、読みとばしていただいても構いません。
証明の概要
ナイトツアーが成立する条件である「すべてのマス目をたった一度だけ通る」ということから、
上の画像のように、角のマス目に移動することができるマス目は必ず２つだけであり、これが４か所の角で成立しているということになります。角を出発地点・終着地点にすることで２か所については無視することができますが、それ以外の２か所については角に移動できるマス目に移動してきたときには必ず角に移動し、そこから角に移動できるマス目で先ほどいなかった方のマス目に移動しなければならない、ということになってしまいます。
つまり、動き方が固定される部分がある、ということです。また、マス目が対称であることを使って総当たり的に、この動き方ではダメ、この動き方でもダメ、これでもダメ、とナイトツアーが成立しないような動き方を探していき、結局すべてのルートがダメでした。という流れで証明を行いました。
まとめ
これまでの結果をまとめると、
自然数\(N\geq5\)に対して、\(N \times N\)のマス目はすべてのマス目をたった一度だけ通るような順路が存在し、自然数\(N\leq4\)に対しては存在しない。
ということになります。
今回紹介したナイトツアーは縦と横のマス目の数が同じような場合でしたが、縦横が異なるマス目についても同様に考えることができますし、３次元以上の次元に拡張して考えることもできたりします。
高次元verについてはこちらを御覧ください。
最後まで読んでいただきありがとうございます！
次回もよろしくお願いします！