第6問

n

を正の整数とする。ノルディック方陣とは、

1

から

n^2

までのすべての整数を、各マスにちょうど一つずつ含む

n\times n

の盤面である。上り坂経路とは、一つ以上のマスからなる列で、次を満たすものである。(a) 列の最初のマスは谷、すなわちそこに書かれた数が直交する隣接マスすべての数より小さい；(b) 列の各後続マスは直前のマスと直交隣接している；(c) 列のマスに書かれた数は増加順である。ノルディック方陣における上り坂経路の総数の最小値を

n

の関数として求めよ。

ステップ 4/5: 先に

T

を埋めて

1

を唯一の谷にする

前のステップ次のステップ

1\in T,\quad T\ \text{filled by adjacency, then the rest arbitrarily}

詳しい解説

$1$ を $T$ の一マスに置き、 $T$ の残りを $2,3,\ldots$ で、新しい数のマスが既に埋まったマスに隣接するように埋める（ $T$ が連結なので常に可能）。最後に残りのマス（ $T$ の外）を大きい数で任意に埋める。すべての外側マスは、すべての外側の数より前に埋まった $T$ のマスにのみ隣接し、 $T$ は $1$ から増加する連結順に埋められたので、盤面全体で唯一の谷は $1$ を含むマスである。