第5問
カタツムリのタートルは、2024行2023列のグリッドの最上段の行にいて、最下段の行に到達したいと考えている。しかし、最初と最後の行を除く各行にちょうど1匹ずつ、合計2022匹の隠れたモンスターがいて、どの二匹も同じ列にはいない。タートルは最初の行から最後の行へ到達するために何度も試行を行う。各試行では、最初の行の好きなマスから出発し、その後は上下左右に隣接するマスへの移動を繰り返す（すでに訪れたマスに戻ることも許される）。もしタートルがモンスターのいるマスに到達すると、その試行は終了し、タートルは最初の行に戻されて新しい試行を始める。モンスターは試行の間に動かず、タートルは自分が訪れた各マスにモンスターがいたかどうかを覚えている。最後の行のいずれかのマスに到達すると、その試行は終了しタートルの勝利となる。モンスターの配置によらず、タートルが高々 回の試行で最下段の行に到達できることを保証する戦略が存在するような、最小の整数 を求めよ。
ざっくり言うと
最初のモンスターが内部にある場合、階段状の経路を端へ向けて進めれば、二匹目がどこに現れてもその上に安全な肩のセルを残せる。二匹目の位置が分かったら、その行を横切って最初のモンスターの既知の安全な列へ移る。
詳しい解説
行を 、列を とし、、、 とする。 の場合は右向きの鏡像階段を使い、それ以外では以下の左向き階段を使う。行2の列 に入り、列 まで西へ進み、行3へ下り、さらに一列西へ進んで下りる、という操作を続ける。行 で最初に入るセルは であり、下る前に一列西へ進む。この経路は に達する。下向きに へ入ったときそこが なら、その右上のセル はすでに安全に訪れている。3回目の試行では安全な接頭部を再現し、 から行 に入り、その行を水平に列 まで進む。 が西向きの移動で見つかった場合は、同じ行でその直後の東側のセルが安全なので、同じ水平な迂回が使える。同じ行の他のセルは がその行唯一のモンスターなので全て安全であり、列 は行2の下では安全である。なぜならそこにはすでに があり、一つの列に二匹のモンスターはないからである。従って列 を最下段まで下りればよい。階段が無傷で に達した場合は、行 を列 まで東へ掃き、下へ進む。その掃引中に出会うモンスターがあればそれは であり同じ行で回避でき、列 のモンスターは不可能である。ここで は現在の行を表し、別の箇所の も同じ行番号である。