MathLabs

第6問

nn を正の整数とする。ノルディック方陣とは、11 から n2n^2 までのすべての整数を、各マスにちょうど一つずつ含む n×nn\times n の盤面である。上り坂経路とは、一つ以上のマスからなる列で、次を満たすものである。(a) 列の最初のマスは谷、すなわちそこに書かれた数が直交する隣接マスすべての数より小さい;(b) 列の各後続マスは直前のマスと直交隣接している;(c) 列のマスに書かれた数は増加順である。ノルディック方陣における上り坂経路の総数の最小値を nn の関数として求めよ。
ステップ 2/5: 大域的な谷における一マス経路を加える
2n2−2n+12n^2-2n+1
詳しい解説

これら 2n(n−1)2n(n-1) 個の自明でない経路のほかに、11 を含む一マスは常に谷であり、一マスだけの上り坂経路をもう一つ与える。したがって、あらゆるノルディック方陣は少なくとも 2n(n−1)+1=2n2−2n+12n(n-1)+1=2n^2-2n+1 個の上り坂経路を持つ。