第6問

n

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

1

から

n^2

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

n\times n

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

n

の関数として求めよ。

ステップ 5/5: この構成がちょうど

2n^2-2n+1

個の経路を持つことを示す

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

2n^2-2n+1

詳しい解説

$1$ が唯一の谷なので、すべての上り坂経路はそのマスから始まる。 $T$ の外側には隣接する二マスがないため、経路が $T$ を出た後に外側のマスを二つ連続して通ることはない。さらに木の増加順序により、各有向辺には谷までの対応する延長がちょうど一つある。したがって下界で数えた $2n(n-1)$ 個の自明でない経路と $1$ の一マス経路が全経路であり、等号が成立する。