MathLabs

第6题

设 nn 为正整数。一个北欧方阵是一个 n×nn\times n 的棋盘，含有从 11 到 n2n^2 的所有整数，每格恰好一个数。一条上坡路径是由一个或多个格子组成的序列，满足：(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 条上坡路径。