Scientific and Educational Reports of the Facultyof Science and Technology, Kochi University
Vol. 1 (2018), No. 3

m×n のすべてのマス目を通る道順の総数について

金城重孝(沖縄県立球陽高等学校 2 年) 山内昌哲(数学クラブ顧問)

概要:この論文では, m×n のすべてのマス目を通る道順の総数のもつ性質を調べている。ｍ＝3 の場合に，道順の総数及び最初の移動を指定したときの道順の総数を求めた。これら結果については参考文献[2]に同様の性質が述べられているが,ここでは，別証明を与えた。この論文の主たる結果は，一般のｍ に対して m×n のすべてのマス目を通る道順の総数を上から評価する不等式を与えたことである。

1．はじめに
沖縄県立球陽高等学校の数学クラブでは，自ら研究課題を設定し，研究をしてゆくという活動を行っている。部員である金城重孝は Hamilton 道について述べられている参考文献[1]の具体例を考え，m×n のすべてのマス目を通る道順の総数について研究をし，次の結果を得た。

( , ) とおく。このとき， ( , ) に対して次m と n を自然数，左上のマス目をスタートして，右下のマス目にゴールする，

定理

m×n のすべてのマス目を通る道順の総数を(1) ｍ＝3，n ≧3 のとき， (3, )＝2の(1)，(2)，(3)が成り立つ：(2) ｍ＝3，n ≧3 のとき，最初の移動で下へ進む場合の道順の総数を( , )≦2 ((3,n) とすると，の移動で右に進む場合の道順の総数を(3))(3,n)＝(3,n)，最初(3,n)＝2.

謝辞 ｍ＝3 の場合の結果を，大阪府立大手前高等学校主催の第 9 回マスフェスタでポスター発表をした際，定理(1)(2)について貴重なアドバイスをいただいた京都大学國府寛司
教授，ならびに定理(3)の証明やこの論文の完成まで終始お世話になった高知大学理工学部
紀要編集委員の方に，心からの感謝を述べたい。

2．定理の証明(定理(1)(2)の証明)

左から s 列目，上から t 段目にあるマス目を(s, t )とし，s と t は1≦s≦3, 1≦t≦n を満たす自然数とする。ここでは，スタート地点(1, 1)からゴール地点通ることができないものとする。このような道順を Hamilton 道と呼ぶことにする。( ,(3, n)まですべてのマス目を通る道順の総数を求める。ただし，一度通ったマス目は再びから（ ,)）まで移動したいとき，最短で進む道順を矢印の記号→で表すことにする。ただし，この記号を用いる場合は， ＝または
1

Received: February 22, 2018
Reviewed by anonymous referee, and accepted: March 7, 2018
Published: March 31, 2018

＝でなければならないとする。R(3,n)

は，3×n のすべてのマス目を通る道順の総数を表す。最初の移動で下へ進む場合の道順の総数を(3,n), 最初の移動で右へ進む場合の道順の総数を(3,n) とする。3×n のマ

ス目において，(1, 1)→（1, k）→(2, k)→(2, 1)→(3, 1)→(3, k)と進む道順の総数を,と表す。このとき，まだ通っていないマス目は 3×(n - k)であり，これは 3×(n－k +1)のマス目で最初に右へ 1 マス進んだ場合の条件を満たす道順の総数に等しい。よって，次が成り立つ。
(3, −=,+ 1) =,3×n のマス目において(1, 1)→(3, 1)→(3, m)→(2, m)→(2, 2)→(1, 2)→(1, m)と進む,道順の総数をと表す。このとき，まだ通っていないマス目は 3×(n－m)であるから，次が成り立つ。
,(3, −=+ 1) =,道順は最初に下へ進む場合と右へ進む場合に大別できるので，次が成り立つ。
(3, ) =(3, ) +n ＝3, 4, 5 において，R(3,n)＝2R(3,n)＝2(3,n)＝,(3, ) =(3,n)＝,(3,n)＝2+,,(3,n) が成り立つことから，(n≧3)と推測できる。これを数学的帰納法により証明する。
[1] n＝3 のとき，次の図 1, 2 の 2 通りの道順が考えられるから，R(3,3)＝2,(3,3)＝(3,3)＝1 が成り立つ。

図1

図2[2] 3 以上 p 以下のすべての自然数 n について R(3,n)＝2は,+ ・・・ +(3, ) に相当する。また，立つとする。に相当し，,は,,+ ・・・ +,+ ・・・ +は,(3,n)＝,(3, )) に相当し，, (＝,+ ・・・ +(3, ) に相当する。よって，次が成り立つ。
(3, + 1) =＝,,++(2,は+ ・・・ +,+ ・・・ +(3,n) が成り,,), (＝,(3, ))(3, )+(3, + 1) =＝,＝
(3, + 1) =(3, + 1) =ゆえに，＝(＝,,+,+＝(3, ) +＝2＋2＝2)＝＋,,,+ ・・・ ++ ・・・ +(3, )(3, ) +(3, )+,)+(,+ ・・・ +,(3, )+(3, ) +よって，n＝p +1 のときにも R(3,n)＝2+,(3,n)＝2,)++(,,+ ・・・ ++ ・・・ +,,))(3, )(3,n)＝，,(3,n)＝2[1]，[2]から，3 以上のすべての自然数 n において R(3,n)＝2(3,n)＝,,＝ (3, ) + (3, )＝2((3, )++ ・・・ +(3, + 1)+,+(,(3, + 1) が成り立つ。また，次が成り立つ。
＝(3, + 1) +＝+,(3, )が成り立つ。
，が成り立つことが示せた。
(証明終)(定理(3)の証明) 1≦s≦m, 1≦t≦n で，s と t は自然数とする。ここでは，スタート地
点(1，1)からゴール地点(m，n)へ移動する n 列 m 段の mn 個のすべての点を通る Hamilton
道の総数を考える。ある点から別の点へは，縦か横のみの移動となる。今，1 段に点が n 個あり，横の線分を引くことを考える。線分は複数本引く，線分を全く引かない，線分上にない点があってもよいものとする。線分の引き方の総数は，自然数 n を n 以下の自然数の和を用いて表す(和の順番も区別する)方法の総数に等しい。自然数 n を 1 が 1 列となって nりが考えられるから,仕切りを入れる方法は 2個並んでいるものと考えると,それぞれの 1 と 1 の間で仕切りを入れるか入れないかの 2 通2通りある。したがって，線分の引き方も通りある。このとき，点の特徴を図 3 のように，線分上にあるが端点でない点 A，線分の端点にある点 B，線分上にない点 C の 3 通りに分類する。

図33では，これから，横の線分を指定した場合，縦の線分のみを引いて Hamilton 道を考える
数 2( , ) を上から評価する不等式を与えることができる。と，その道順は多くても 1 通りであることを示そう。そうすれば，横の線分の引き方の総の m 乗で，その総数まず，スタート地点を含む段に横の線分を指定する。次に，スタート地点を含む段から 1段ずつ進んで縦の線分を引くことを考える。今，横の線分が指定されているので，道順に違いができるのは縦の線分となる。Hamilton 道は同じ点を 2 回通ることができないので，横の線分が等しく，縦の線分が異なる Hamilton 道が存在しない。よって，道順に違いができる縦の線分を引くとき，横の線分の端点から縦の線分を上に引く場合と下に引く場合を考えればよい。ここでは，縦の線分を下に引く場合だけを示す。縦の線分を上に引く場合は，縦の線分を下に引く場合と同様に示すことができる。
点の特徴を図 3 のように 3 通りに分類したので，縦の線分を下に引いた先の点は，次の
図 4，5，6 のような線分上にあるが端点でない点 A， 線分の端点 B，線分上にない点 C の場合に分けることができる。

図4

図5

図6

まず，図 4 の場合は点 A に到達したとき，点 A を 2 回通らないと指定された横の線分を通ることができない。よって，この場合は Hamilton 道が得られない。次に，図 5 の場合は横の線分 BD が指定されているので，点 B に到達すれば点 D へ進まければならない。よって，
点 B から次へ進む道順は一意的である。今，横の線分が指定されているので，図 6 の場合は点 C から次の段へ縦の線分を下に引いて進まなければならない。よって，点 C から進む道順は一意的である。一方，縦の線分を上に引く場合についても，図 4，5，6 で示したよ
うにその道順は多くても 1 通りである。図 5 において，点 D から更に進めて道順を決める
場合は縦の線分を下に引かなければならない。よって，点 D から進む道順は一意的である。
ゆえに，Hamilton 道は横の線分を指定した場合，縦の線分を引いた先の点の特徴が図 4，以上より，m×n のすべてのマス目を通る道順の総数( , ) を，横の線分の引き方の総5，6 のように分類されるので，その道順は多くても 1 通りであることが示せた(*)。
数 2の m 乗，すなわち 2 ()を用いて上から評価する不等式を与えることができた。
(証明終)定理(3)の証明の(*)より，次の系が成り立つ。

系

横の線分が等しく，縦の線分が異なる Hamilton 道は存在しない。
4

参考文献[1] K. L. Collins and L.B. Krompart, The number of Hamiltonian paths in a rectangulargrid, Discrete Math. 169(1997), 29-38.
[2] 2015 日本数学コンクールのまとめ，ジャングルジムの最長経路問題, pp.18-29，名古屋大学日本数学コンクール委員会編.

5