第6题

设

n

为正整数。一个北欧方阵是一个

n\times n

的棋盘，含有从

1

到

n^2

的所有整数，每格恰好一个数。一条上坡路径是由一个或多个格子组成的序列，满足：(a) 序列的第一个格子是谷，即其数小于其所有正交相邻格子的数；(b) 序列中每个后续格子都与前一个格子正交相邻；(c) 序列中各格子的数递增。求北欧方阵中上坡路径总数的最小可能值，用

n

的函数表示。

第 4/5 步：先填

T

使

1

成为唯一的谷

上一步下一步

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

详细分析

把 $1$ 放在 $T$ 的一个格子中，再用 $2,3,\ldots$ 填满 $T$ 的其余部分，使每个新数所在的格子都与已填的格子相邻（因 $T$ 连通总能做到），最后用较大的数任意填满剩余（ $T$ 之外）的格子。由于每个外部格子只与在所有外部数之前已填的 $T$ 格子相邻，且 $T$ 是从 $1$ 开始按连通递增顺序填的，整个棋盘唯一的谷就是含 $1$ 的格子。