第6問

n

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

1

から

n^2

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

n\times n

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

n

の関数として求めよ。

ステップ 3/5: 外側の二マスが隣接しない木

T

を構成する

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

ざっくり言うと

選んだ木の外側にあるすべてのマスが木のマスだけに囲まれているなら、上り坂経路が二つの連続する外側マスを通ることは決してなく、経路の伸び方が大きく制限される。

T\text{ is a periodic tree whose complement has no adjacent cells}

詳しい解説

標準的な周期構成（必要なら境界の行または列を切り詰める）により、連結な木 $T$ で $T$ の外側の二マスが直交隣接しないものを得る。個数の議論ではこの構造的性質だけを用いる。