こんにちは。東久留米市の学習塾塾長です。
今回は、２０１９年日本ジュニア数学オリンピック本選に出題された組合せの問題を取り上げます。
問題は、
「ｎを３以上の奇数とする。ｎ×ｎのマス目を使って次のようなゲームを行った。
● マスを１つ選び、駒を置く。
● その後、駒が置いてあるマスに縦、横、斜めに隣りあうマスの中から今まで駒が訪れていないようなマスを１つ選び、駒を移動させる。この操作を駒が移動できなくなるまで繰り返す。
駒が
のマスすべてを訪れていたとき、駒が縦または横に移動した回数としてありうる最小の値を求めよ。」
です。
早速、取り掛かりましょう。
例えば、図１のように５×５のマス目で試行してみると、縦と横への移動を極力避けながら、すべてのマスを訪れる経路の一つが、図１に示すように、Ａを出発した後、横（右）に１マス移動→斜め（左下）に１マス移動→縦（下）に１マス移動→斜め（右上）に２マス移動→・・・→Ｂ であることは容易に想像できます。
▲図１．５×５のマス目で試行します
このとき、縦の移動と横の移動はいずれも４回で、これらは、隣接する行間の移動回数の和と列間の移動回数の和です。
したがって、ｎ×ｎのマス目で図１のように移動した場合、縦と横の移動回数は、いずれもｎ－１（回）で、合計２ｎ－２（回）が可能になります。
そこで、与えられた条件を満たす移動で、縦と横に移動する回数が２ｎ－２（回）未満にならないことを示しましょう。
図２のように、奇数行奇数列のマスをＰ、偶数行偶数列のマスをＱ、奇数行偶数列のマスをＲ、偶数行奇数列のマスをＳとするｎ×ｎのマス目を考えます。このとき、斜めの移動が可能なのは、Ｐ－Ｑ間とＲ－Ｓ間だけであることに留意しましょう。
▲図２．奇数行奇数列のマスをＰ、偶数行偶数列のマスをＱ、奇数行偶数列のマスをＲ、偶数行奇数列のマスをＳとしました
初めに、Ｐ、Ｑ、Ｒ、Ｓそれぞれのマスの個数を計算すると、それらは、それぞれ、
になります。
ここで、
（１）Ｐのマスを出発してＰのマスに到着する場合
（２）Ｐのマスを出発してＱ、Ｒ、Ｓのいずれかのマスに到着する場合
（３）Ｑ、Ｒ、Ｓのいずれかのマスを出発してＰのマスに到着する場合
（４）Ｑ、Ｒ、Ｓのいずれかのマスを出発してＱ、Ｒ、Ｓのいずれかのマスに到着する場合
のそれぞれにおける、Ｐのすべてのマスについての駒の出入りを調べます。
（１）Ｐのマスを出発してＰのマスに到着する場合
Ｐのすべてのマスについての駒の出入り総数は、（Ｐのコマの個数）×２－２から
です。
このうち、斜めの移動回数の上限は、（Ｑのマス目の個数）×２なので、縦と横の移動回数の下限は、
になります。
（２）Ｐのマスを出発してＱ、Ｒ、Ｓのいずれかのマスに到着する場合
Ｐのすべてのマスについての駒の出入り総数は、（Ｐのコマの個数）×２－１から
です。
このうち、斜めの移動回数の上限は、（Ｑのマス目の個数）×２なので、縦と横の移動回数の下限は、
になります。
（３）Ｑ、Ｒ、Ｓのいずれかのマスを出発してＰのマスに到着する場合
Ｐのすべてのマスについての駒の出入り総数は、（Ｐのコマの個数）×２－１から
です。
このうち、斜めの移動回数の上限は、（Ｑのマス目の個数）×２なので、縦と横の移動回数の下限は、
になります。
（４）Ｑ、Ｒ、Ｓのいずれかのマスを出発してＱ、Ｒ、Ｓのいずれかのマスに到着する場合
Ｐのすべてのマスについての駒の出入り総数は、（Ｐのコマの個数）×２から
です。
このうち、斜めの移動回数の上限は、（Ｑのマス目の個数）×２なので、縦と横の移動回数の下限は、
になります。
以上から、縦と横の移動回数の下限は、（１）のＰのコマを出発してＰのコマに到着する場合に最も小さくなり、その値は２ｎ－２（回）で、２ｎ－２(回）未満になることはありません。
したがって、縦または横に移動した回数としてありうる最小の値は ２ｎ－２（回） でこれが答えです。
簡単な問題です。
今回は、２０１９年日本ジュニア数学オリンピック本選に出題された組合せの問題を取り上げます。
問題は、
「ｎを３以上の奇数とする。ｎ×ｎのマス目を使って次のようなゲームを行った。
● マスを１つ選び、駒を置く。
● その後、駒が置いてあるマスに縦、横、斜めに隣りあうマスの中から今まで駒が訪れていないようなマスを１つ選び、駒を移動させる。この操作を駒が移動できなくなるまで繰り返す。
駒が
のマスすべてを訪れていたとき、駒が縦または横に移動した回数としてありうる最小の値を求めよ。」
です。
早速、取り掛かりましょう。
例えば、図１のように５×５のマス目で試行してみると、縦と横への移動を極力避けながら、すべてのマスを訪れる経路の一つが、図１に示すように、Ａを出発した後、横（右）に１マス移動→斜め（左下）に１マス移動→縦（下）に１マス移動→斜め（右上）に２マス移動→・・・→Ｂ であることは容易に想像できます。
▲図１．５×５のマス目で試行します
このとき、縦の移動と横の移動はいずれも４回で、これらは、隣接する行間の移動回数の和と列間の移動回数の和です。
したがって、ｎ×ｎのマス目で図１のように移動した場合、縦と横の移動回数は、いずれもｎ－１（回）で、合計２ｎ－２（回）が可能になります。
そこで、与えられた条件を満たす移動で、縦と横に移動する回数が２ｎ－２（回）未満にならないことを示しましょう。
図２のように、奇数行奇数列のマスをＰ、偶数行偶数列のマスをＱ、奇数行偶数列のマスをＲ、偶数行奇数列のマスをＳとするｎ×ｎのマス目を考えます。このとき、斜めの移動が可能なのは、Ｐ－Ｑ間とＲ－Ｓ間だけであることに留意しましょう。
▲図２．奇数行奇数列のマスをＰ、偶数行偶数列のマスをＱ、奇数行偶数列のマスをＲ、偶数行奇数列のマスをＳとしました
初めに、Ｐ、Ｑ、Ｒ、Ｓそれぞれのマスの個数を計算すると、それらは、それぞれ、
になります。
ここで、
（１）Ｐのマスを出発してＰのマスに到着する場合
（２）Ｐのマスを出発してＱ、Ｒ、Ｓのいずれかのマスに到着する場合
（３）Ｑ、Ｒ、Ｓのいずれかのマスを出発してＰのマスに到着する場合
（４）Ｑ、Ｒ、Ｓのいずれかのマスを出発してＱ、Ｒ、Ｓのいずれかのマスに到着する場合
のそれぞれにおける、Ｐのすべてのマスについての駒の出入りを調べます。
（１）Ｐのマスを出発してＰのマスに到着する場合
Ｐのすべてのマスについての駒の出入り総数は、（Ｐのコマの個数）×２－２から
です。
このうち、斜めの移動回数の上限は、（Ｑのマス目の個数）×２なので、縦と横の移動回数の下限は、
になります。
（２）Ｐのマスを出発してＱ、Ｒ、Ｓのいずれかのマスに到着する場合
Ｐのすべてのマスについての駒の出入り総数は、（Ｐのコマの個数）×２－１から
です。
このうち、斜めの移動回数の上限は、（Ｑのマス目の個数）×２なので、縦と横の移動回数の下限は、
になります。
（３）Ｑ、Ｒ、Ｓのいずれかのマスを出発してＰのマスに到着する場合
Ｐのすべてのマスについての駒の出入り総数は、（Ｐのコマの個数）×２－１から
です。
このうち、斜めの移動回数の上限は、（Ｑのマス目の個数）×２なので、縦と横の移動回数の下限は、
になります。
（４）Ｑ、Ｒ、Ｓのいずれかのマスを出発してＱ、Ｒ、Ｓのいずれかのマスに到着する場合
Ｐのすべてのマスについての駒の出入り総数は、（Ｐのコマの個数）×２から
です。
このうち、斜めの移動回数の上限は、（Ｑのマス目の個数）×２なので、縦と横の移動回数の下限は、
になります。
以上から、縦と横の移動回数の下限は、（１）のＰのコマを出発してＰのコマに到着する場合に最も小さくなり、その値は２ｎ－２（回）で、２ｎ－２(回）未満になることはありません。
したがって、縦または横に移動した回数としてありうる最小の値は ２ｎ－２（回） でこれが答えです。
簡単な問題です。