第6题

设

n

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

n\times n

的棋盘，含有从

1

到

n^2

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

n

的函数表示。

第 1/5 步：每对相邻格子都产生一条非平凡上坡路径

通俗地说

将每条边从较大数指向较小数，并沿递减数值走到某个谷。反向这条路径便得到一条包含所选边的上坡路径。

2n(n-1)

详细分析

对网格的 $2n(n-1)$ 条边分别向下定向，并将下坡行走延长到某个谷。反向后得到非平凡上坡路径。不同有向边得到的路径彼此不同，因此每个方阵至少有 $2n(n-1)$ 条非平凡上坡路径。