MathLabs

第6题

设 nn 为正整数。一个北欧方阵是一个 n×nn\times n 的棋盘，含有从 11 到 n2n^2 的所有整数，每格恰好一个数。一条上坡路径是由一个或多个格子组成的序列，满足：(a) 序列的第一个格子是谷，即其数小于其所有正交相邻格子的数；(b) 序列中每个后续格子都与前一个格子正交相邻；(c) 序列中各格子的数递增。求北欧方阵中上坡路径总数的最小可能值，用 nn 的函数表示。
第 3/5 步：构造一棵树 TT，使任意两个外部格子都不相邻
上一步下一步
通俗地说

如果所选树之外的每个格子都只被树中的格子包围，那么上坡路径就永远不会经过两个连续的外部格子，这严格限制了路径的增长方式。

T is a periodic tree whose complement has no adjacent cellsT\text{ is a periodic tree whose complement has no adjacent cells}
详细分析

采用标准的周期构造（必要时删去边界行或列），可得到一棵连通树 TT，使 TT 外任意两格不正交相邻。计数中只使用这一结构性质。