第6题

设

n

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

n\times n

的棋盘，含有从

1

到

n^2

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

n

的函数表示。

第 5/5 步：证明该构造恰好有

2n^2-2n+1

条路径

2n^2-2n+1

详细分析

由于 $1$ 是唯一的谷，每条上坡路径都从它所在格子出发。 $T$ 外没有相邻格子，因此路径离开 $T$ 后不可能连续经过两个外部格子；结合树中的递增填法，每条有向边恰有一条延伸到谷。于是下界中的 $2n(n-1)$ 条非平凡路径与 $1$ 处的一格路径正好涵盖全部路径，得到等号。