第6問

n

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

1

から

n^2

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

n\times n

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

n

の関数として求めよ。

ステップ 1/5: 隣接する各対が自明でない上り坂経路を生む

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

ざっくり言うと

各辺を大きい数から小さい数へ向け、谷に達するまで値を減らして進む。この歩みを逆にすると、選んだ辺を含む上り坂経路が得られる。

2n(n-1)

詳しい解説

格子の $2n(n-1)$ 本の辺それぞれを下向きに向け、下り坂の歩みを谷まで延長する。逆向きにすれば自明でない上り坂経路が得られる。異なる有向辺から得た経路は異なるので、どの方陣にも少なくとも $2n(n-1)$ 個の自明でない上り坂経路がある。