JJMO本選2019問4

答え\(\cdots 2n-2\)
【略解】
個人的には時間もかけずあっさり解けた問題で、問1よりも先に解けたくらいなのですが、出来は(恐らく)そこまでよくなかったらしいです。
ただし、答えの予想くらいは駒を実際に動かしていけばすぐにわかりますから、そのくらいは解答して部分点を狙うべきでしょう。
ちなみに、僕がこの問題を解けたのは、先日、SNSで

「将棋の銀の駒を端っこのマスに置く。銀の動きに沿って全てのマスを1回ずつ通ることは可能か。」

という問題を見て、解いたことがあるからかも知れません。
銀という駒は横に動けないという大きな特徴があります。そのため、上から順に1行目,2行目,…,9行目とすれば、奇数行目から偶数行目、偶数行目から奇数行目に動くしかありません。
しかし、奇数行目のマスは45マス、偶数行目のマスは36マスなので、どうやっても奇数行目のマスが余ってしまうのです。
この問題についてもほぼ同じアプローチで解決します。
縦、横それぞれに何回ずつの操作が最低でも必要かを考えましょう。

【略解】
(最小性)
斜め、縦のみの移動では奇数行目から偶数行目に、偶数行目から奇数行目にしか移動できないので、ます目全体で奇数行目のマスは偶数行目のマスより\(n\)個多いから、横の移動回数を下から押さえると、(奇数行目からスタートして)少なくとも\(n-1\)回は横に移動する必要がある。同様に、縦の移動も\(n-1\)回はする必要がある。

(実例)
また、左上からスタートし、1行目と2行目を斜め移動で交互に進み、右上についたら1つ下に移動して斜め移動で1行目と2行目を交互に進み、2行目の左端に来たら1つ下に移動する。
同じ要領で3行目と4行目、5行目と6行目、\(\cdots\)、\(n-2\)行目と\(n-1\)行目を通過し、\(n-1\)行目の左端に来たら、1個下に移動して、\(n\)行目はまっすぐ左から右へ横に移動しておけば、このとき、縦と横の移動は\(n-1\)回ずつ。

以上より求める最小値は\(2n-2\)

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です