第5問
カタツムリのタートルは、2024行2023列のグリッドの最上段の行にいて、最下段の行に到達したいと考えている。しかし、最初と最後の行を除く各行にちょうど1匹ずつ、合計2022匹の隠れたモンスターがいて、どの二匹も同じ列にはいない。タートルは最初の行から最後の行へ到達するために何度も試行を行う。各試行では、最初の行の好きなマスから出発し、その後は上下左右に隣接するマスへの移動を繰り返す（すでに訪れたマスに戻ることも許される）。もしタートルがモンスターのいるマスに到達すると、その試行は終了し、タートルは最初の行に戻されて新しい試行を始める。モンスターは試行の間に動かず、タートルは自分が訪れた各マスにモンスターがいたかどうかを覚えている。最後の行のいずれかのマスに到達すると、その試行は終了しタートルの勝利となる。モンスターの配置によらず、タートルが高々 回の試行で最下段の行に到達できることを保証する戦略が存在するような、最小の整数 を求めよ。
ざっくり言うと
タートルが行2で最初に足を踏み入れるマスにはモンスターがいる可能性があり、次の試行で行3に初めて足を踏み入れる新しいマスにも同様にモンスターがいる可能性があるため、二回の失敗を免れる固定戦略は存在しない。
詳しい解説
タートルの最初の試行では、行 に初めて足を踏み入れた瞬間に、敵がそこにモンスターを置いていた可能性があり、その時点で試行は終了する。二回目の試行では、タートルはどこかの列で初めて行 に入らなければならないが、敵はそこにも再びモンスターを置いていた可能性がある。これは、いかなる戦略も 回未満の試行で成功を保証できないことを示しており、したがって である。