第 6 章　怎么折腾都不变的东西

第三件工具，是我个人最喜欢的一件，叫不变量。

很多奥数题长这样：给你一个初始局面，一条"允许的操作"，让你把局面变来变去，问你**“能不能变到某个目标局面？”** 比如一堆数让你反复加加减减，问能不能最后凑出 0；一块棋盘让你摆骨牌，问能不能铺满。

新手一上来就埋头试：这么变、那么变……试到天黑也说不清"到底能不能"。因为"能"只要找出一条路就行，"不能“却要堵死所有路——你试一万次失败，也不算证明。

不变量专治这个"不能”。它的思路简单到狡猾：

在所有这些操作下，找出一个怎么折腾都不变的量。 如果初始局面这个量是甲，目标局面这个量是乙，而甲 $\ne$ 乙，那就永远变不过去——一次都不用试。

这就像看一个上了锁的房间：不管屋里的人怎么搬家具，墙的总数不会变。你要是听说目标房间墙多了一面，那不用进去看，就知道根本到不了。

一、最经典的一块缺角棋盘

例 6.1（☼☼，残缺棋盘问题）一张 $8\times 8$ 的棋盘，挖掉对角的两个角（左上角和右下角那两格）。剩下 62 格。问：能不能用 31 块 $1\times 2$ 的骨牌（每块盖住相邻两格）正好把它铺满？

新手会拿骨牌摆半天，总差那么一两格，但摆不出不等于摆不成。我们找不变量。

给棋盘照常染黑白色（国际象棋那样，相邻格异色）。关键观察：每一块 $1\times 2$ 的骨牌，无论横竖，必定盖住一黑一白两格。 所以你每放一块，盖掉的黑格数和白格数总是相等——“已盖黑格数减已盖白格数"恒等于 0，这就是不变量。 真要铺满，整块盘的黑白格数就必须相等。

再看那两个被挖掉的角。国际象棋盘上，对角的两个角是同色的（比如都是白格）。挖掉两个白格，剩下的 62 格里，黑格 32 个、白格 30 个，黑白不等。

骨牌只会一黑一白成对地盖，永远盖不平这 32 对 30 的差额。所以无论怎么摆，都铺不满。就这样。

你看，我们一块骨牌都没真摆，靠的是"每块骨牌盖一黑一白"这条铁律。染色，是造不变量最常用的一招——把格子染成两种、三种或更多颜色，让"允许的操作"对颜色的影响变得有规律。

最朴素、最常用的不变量，是奇偶性（一个数是奇是偶）。很多操作会改变具体数值，却保住奇偶，这时奇偶就是你的不变量。

例 6.2（☼☼，经典黑板问题）黑板上写着 $1,2,3,\dots,1989$ 这 1989 个数。每次操作：擦掉任意两个数 $a,b$，把它们的差的绝对值 $|a-b|$ 写回去。 这样数会越来越少，最后只剩一个数。问：这最后剩下的数，可能是 0 吗？

又是"能不能”，又该找不变量。盯住全部数之和的奇偶性。

每次操作，把 $a,b$ 换成 $|a-b|$，总和的变化是

$$\big(a+b\big)-|a-b| = 2\cdot\min(a,b),$$

这是个偶数。也就是说，每次操作，总和顶多变动一个偶数——总和的奇偶性，从头到尾不变。 这就是我们的不变量。

初始总和是

$$1+2+\cdots+1989=\frac{1989\times 1990}{2}=1989\times 995,$$

两个奇数相乘还是奇数。既然总和的奇偶性永不改变，那么不管你怎么擦怎么写，最后剩的那个数也必是奇数。而 0 是偶数。

所以最后剩的数不可能是 0。就这样。

这道题再次示范：不要去试，去找那个"任你折腾、岿然不动"的量。这里它是"总和模 2"。

不变量不会写在题面上，得你去造。常见的几个矿脉，挖题时挨个试：

找到候选量后，只验一件事：每做一次允许的操作，这个量是不是真的不变（或只按固定规律变）。 验过了，它就是你的铁证。

上手清单（“能不能变到……“型题）
先问自己：这是"能”（找一条路）还是"不能”（堵死所有路）？不变量主攻"不能"。
在上面四条矿脉里找一个候选不变量。
验证：每次操作它确实不变。
算初始局面和目标局面的这个量。两者不等 → 永远到不了，证毕。

（注意一个边界：不变量相等，不直接保证"一定能到达"——它只擅长证"到不了"。要证"能到达"，多半得真的把路构造出来，那是第 9 章的事。）

这一章要带走的东西：

就这样。