组合数学与离散数学

不变量与单调量

在组合过程的每一步操作下保持不变或单调变化的量,用于证明不可能性与终止性。

直观为什么有些谜题永远无解

从 $8\times 8$ 国际象棋棋盘上去掉两个对角格子,剩下 $62$ 个格子。能否用 $31$ 张 $2\times 1$ 的骨牌铺满剩余棋盘?手工尝试每次都会失败,但骨牌摆法有数百万种。与其逐一穷举,不如观察颜色:每张骨牌总是恰好覆盖 $1$ 个黑格和 $1$ 个白格,因此 $31$ 张骨牌必须覆盖 $31$ 个黑格与 $31$ 个白格。然而棋盘的两个对角格颜色相同,剩下的格子必然是一种颜色 $32$ 个、另一种颜色 $30$ 个!差值 $W - B$ 是骨牌放置下的不变量,一行即可证明不可能。

二分图着色作为不变量:每条边(骨牌)连接两侧各一个顶点,因此任何完美匹配都要求两侧顶点数相等。

大学定义:不变量与单调量

定义: 状态系统的不变量与单调量

考虑状态空间为 $\mathcal{S}$ 、合法转移为 $s \to s'$ 的组合过程。若函数 $I: \mathcal{S} \to X$ 对每一步合法转移 $s \to s'$ 都满足 $I(s') = I(s)$ ,则称其为不变量。若实值函数 $M: \mathcal{S} \to \mathbb{R}$ 在每一步合法转移下满足 $M(s') < M(s)$ (严格递减)或 $M(s') > M(s)$ (严格递增),则称其为单调量(或势函数)。

I(s_0) = I(s_1) = \cdots = I(s_k) \implies \text{if } I(s_{\mathrm{target}}) \neq I(s_0),\ s_{\mathrm{target}} \text{ is unreachable}

M(s_0) > M(s_1) > M(s_2) > \cdots \ge 0,\quad M(s) \in \mathbb{N} \implies \text{process terminates in } \le M(s_0) \text{ steps}

竞赛与研究中常见的不变量与单调量模式
工具	常见形式	所证结论
奇偶不变量	$S \bmod 2$ 或 $(-1)^{\text{inversions}}$	目标状态不可达
模/代数不变量	$\sum a_i \bmod m$ 或多项式求值	最终构型唯一确定
整数值单调量	$M(s) \in \mathbb{N}$ 且 $M(s') \le M(s) - 1$	过程必在 $\le M(s_0)$ 步内终止

大学核心定理:15数码奇偶性与单调量终止定理

定理: 15数码谜题的洛伊德—约翰逊奇偶不变量

在 $4\times 4$ 滑动 $15$ 数码谜题中,设 $N(s)$ 为数字块的逆序数(按行优先顺序编号 $i > j$ 但数字 $i$ 出现在数字 $j$ 之前的数对 $(i,j)$ 个数), $r(s) \in \{1,2,3,4\}$ 为空格所在行号(或等价地设 $d(s)$ 为空格到右下角的曼哈顿距离)。则奇偶性 $(N(s) + r(s)) \bmod 2$ 在每一步合法滑动下保持不变。特别地,仅交换 $14$ 与 $15$ 两个数字块的初始局面无解。

为什么成立?

水平滑动完全不改变 $15$ 个数字块的行优先排列顺序;而垂直滑动会使一个数字块在行优先顺序中恰好跨过 $3$ 个其他数字块(使逆序数改变 $\pm 1$ 或 $\pm 3$ ,必为奇数),同时使空格行号 $r(s)$ 改变 $\pm 1$ 。

证明

第一步(水平滑动)。 当空格在同一行内左右滑动时, $15$ 个数字块按行优先顺序排列的次序完全不变,且空格仍处于第 $r(s)$ 行。因此 $\Delta N = 0$ 且 $\Delta r = 0$ , $N(s) + r(s)$ 保持不变。

第二步(垂直滑动)。 当空格上下滑动时,移入空格原位置的数字块 $t$ 在 $15$ 个数字块的行优先序列中恰好移动 $3$ 个位置。跨过这 $3$ 个数字块中的每一个都会翻转数对 $(t, u)$ 的逆序关系,使 $N(s)$ 每次改变 $+1$ 或 $-1$ 。总变化量 $\Delta N \in \{-3, -1, +1, +3\}$ 必为奇数。与此同时 $\Delta r \in \{-1, +1\}$ 也是奇数,故 $\Delta(N + r)$ 为偶数。

第三步(交换14与15)。 在空格固定于第 $r = 4$ 行时仅交换数字块 $14$ 与 $15$ ,会使 $N(s)$ 增加 $+1$ (从 $0$ 变为 $1$ )而 $\Delta r = 0$ 。于是初始状态( $1 + 4 \equiv 1 \pmod 2$ )与复原状态( $0 + 4 \equiv 0 \pmod 2$ )的 $(N + r) \bmod 2$ 不同,证明任何合法滑动序列都无法到达复原状态。

定理: 良序单调量终止定理

设某过程的每一步合法转移 $s \to s'$ 都使整数值函数 $M: \mathcal{S} \to \mathbb{Z}$ 至少减少 $1$ ,即 $M(s') \le M(s) - 1$ ,且对所有状态 $s \in \mathcal{S}$ 有 $M(s) \ge 0$ 。则从任意初始状态 $s_0$ 出发,该过程必在至多 $M(s_0)$ 步内终止。

为什么成立?

如果楼梯高 $M(s_0)$ 级,每一步至少下一级且不能低于地面 $0$ ,那么下楼步数不可能超过 $M(s_0)$ 步。

证明

**第一步( $k$ 步后的递推界)。** 设 $s_0 \to s_1 \to s_2 \to \cdots \to s_k$ 为任意一条长为 $k$ 的合法转移序列。对 $i = 1, 2, \dots, k$ 应用条件 $M(s_{i}) \le M(s_{i-1}) - 1$ 并累加消去中间项,得 $M(s_k) \le M(s_0) - k$ 。

**第二步( $k$ 的上界)。** 由于对每个可达状态 $s_k \in \mathcal{S}$ 都有 $M(s_k) \ge 0$ ,联立两式得 $0 \le M(s_k) \le M(s_0) - k$ ,移项即得 $k \le M(s_0)$ 。因此不存在长度 $k > M(s_0)$ 的合法轨迹,过程必在至多 $M(s_0)$ 步内终止。

进阶实际应用与典型例题

在形式化验证与软件工程中,循环不变量与秩函数(单调量)是定理证明器(Lean、Coq、Dafny)证明关键算法结果正确且绝不陷入死循环的标准工具。在分布式共识与筹码激发网络中,代数不变量决定了哪些负载均衡状态是可达的。

例题: 擦去两数并写下其差

黑板上写有 $1, 2, 3, \dots, 2026$ 。每次擦去任意两个数 $a, b$ 并写上 $|a - b|$ ,直到只剩一个数。最后剩下的数能否为 $0$ ?

解答

注意到 $|a - b| \equiv a + b \pmod 2$ ,因为 $(a + b) - |a - b| = 2\min(a,b)$ 恒为偶数。因此黑板上所有数之和的奇偶性 $S \bmod 2$ 是一个不变量!

初始总和为 $S_0 = \frac{2026 \times 2027}{2} = 1013 \times 2027$ 。由于 $1013$ 与 $2027$ 都是奇数, $S_0$ 为奇数( $S_0 \equiv 1 \pmod 2$ )。经过 $2025$ 步后,唯一剩下的数仍须满足与 $S_0 \equiv 1 \pmod 2$ 同余,必为奇数,绝不可能为 $0$ 。

例题: 解开平面上相交的线段

平面上一般位置有 $n$ 个红点和 $n$ 个蓝点,用 $n$ 条线段将它们两两配对。每当两条线段 $A_1B_1$ 与 $A_2B_2$ 相交时,就将其替换为 $A_1B_2$ 与 $A_2B_1$ 。证明该过程必在有限步内终止,最终没有任何相交线段。

解答

定义势函数 $L(s) = \sum_{i=1}^n |A_iB_i|$ 为 $n$ 条线段的欧氏总长度。当 $A_1B_1$ 与 $A_2B_2$ 交于点 $P$ 时,对 $\triangle A_1 P B_2$ 和 $\triangle A_2 P B_1$ 应用三角不等式可得 $|A_1B_2| + |A_2B_1| < (|A_1P| + |PB_2|) + (|A_2P| + |PB_1|) = |A_1B_1| + |A_2B_2|$ 。

因此 $L(s)$ 是每一步下严格递减的单调量!由于 $n$ 个红点与 $n$ 个蓝点之间总共只有 $n!$ 种配对方式, $L(s)$ 至多取 $n!$ 个不同数值,不可能减少超过 $n! - 1$ 次。故该过程必在至多 $n! - 1$ 步内终止。

为什么去掉两个对角格的 $8\times 8$ 棋盘无法用 $31$ 张 $2\times 1$ 骨牌铺满?

从五个数 $1, 2, 3, 4, 5$ 开始,每一步可以给其中任意两个数各加 $1$ 。这五个数能否变得全部相等?

非负整数值单调量 $M(s) \in \mathbb{N}$ 从 $M(s_0) = 42$ 出发,每一步满足 $M(s') \le M(s) - 3$ 。过程终止前最多能进行多少步?

每次将两个数 $a, b$ 替换为 $a + b + ab$ 时,整个列表中保持不变的代数量是什么?

参考文献

Arthur Engel (1998). Problem-Solving Strategies · DOI:10.1007/b97682
Jessica Striker (2017). Dynamical Algebraic Combinatorics: Promotion, Rowmotion, and Resonance · DOI:10.1090/noti1539