初中竞赛组合：不变量与染色构造

不变量与染色是初中竞赛组合题的高频工具。很多“过程变化类”题目，直接算终态很难，但抓住一个在操作中始终不变（或按固定规律变化）的量，就能快速判定“能否达到”与“最少步数”。

一、核心知识点

1. 不变量

不变量是指在允许操作下保持不变的量，常见有：

• 奇偶性（和、差、个数）
• 余数类（模 2、模 3、模 4）
• 颜色数量差（黑白格差）
• 置换奇偶性

常用思路：

1. 先定义一个量 $I$（如元素和的奇偶性）。
2. 验证每次操作对 $I$ 的影响。
3. 比较初态与目标态的 $I$，若冲突则不可达。

2. 单调量与半不变量

有些量不是严格不变，但总是单调增加或减少，可用于证明过程终止或步数下界。

例如：每次操作都使“逆序对个数”减少至少 1，则过程有限步终止。

3. 染色法

把对象按规则染色（棋盘黑白、模类染色、分区染色），把局部操作转化为颜色计数问题。

常见用途：

• 覆盖问题（多米诺、L 形骨牌）
• 跳跃问题（每步跨越特定格）
• 图论分组（奇偶层）

二、例题精讲

例题 1（奇偶不变量）

黑板上写有 10 个整数。每次可任选两个数 $a,b$，擦去并写上 $a+b-1$。操作 9 次后只剩一个数。问该数奇偶性是否由初始状态唯一确定？

点击查看解析

设所有数之和为 $S$。一次操作后，

$$S' = S-a-b+(a+b-1)=S-1.$$

即每次操作总和减 1。共做 9 次，最终数为

$$S_{\text{final}}=S_0-9.$$

故最终奇偶性只由初始总和 $S_0$ 决定，唯一确定。

例题 2（模不变量）

有一枚棋子在数轴 0 点。每次可向左 3 格或向右 5 格。问能否到达点 1？

点击查看解析

设向右走 $x$ 次，向左走 $y$ 次，则位置为

$$5x-3y.$$

要到 1，即

$$5x-3y=1.$$

模 3 得 $2x\equiv1\pmod3$，即 $x\equiv2\pmod3$，可取 $x=2$。 代入得 $10-3y=1\Rightarrow y=3$，可行。

故可以到达点 1（如右右左左左）。

例题 3（棋盘染色）

8x8 棋盘删去两个同色角格后，能否用 1x2 多米诺骨牌覆盖剩余 62 格？

点击查看解析

黑白染色后，原棋盘黑白各 32 格。同色角格被删去后，黑白数量变为 30 和 32（或 32 和 30），不相等。

每个 1x2 骨牌必覆盖 1 黑 1 白，因此总覆盖区域黑白数必须相等。矛盾。

故不可覆盖。

例题 4（构造与不变量结合）

桌上有 15 枚硬币，全是正面。每次可翻转恰好 4 枚。问能否经过若干次操作使得恰有 14 枚反面？

点击查看解析

记反面数为 $k$。每次翻转 4 枚，相当于“若干正变反 + 若干反变正”，故 $k$ 的奇偶性与 4 的奇偶有关：

一次操作对 $k$ 的改变量为

$$\Delta k = (\text{正变反数})-(\text{反变正数}),$$

且两者和为 4，因此 $\Delta k$ 为偶数。

所以 $k$ 的奇偶性不变。初始 $k=0$ 为偶数，目标 $k=14$ 也是偶数，不被排除。

再构造：先翻转第 1,2,3,4 枚得 4 反；再翻 1,2,5,6 得 6 反；持续可实现任意不超过 15 的偶数反面数，故 14 可达。

三、解题策略

1. 先判定题型是否“过程变化 + 可达性判断”。
2. 优先尝试奇偶、模数、颜色计数三个最常见不变量。
3. 若可达性未被否定，再补“构造步骤”证明可达。
4. 对最少步数类题，尝试单调量建立下界。

四、章内练习（折叠答案）

练习 A

有 7 个数，每次选两个数同时加 1。问“所有数之和的奇偶性”是否会改变？

点击查看过程与答案

每次操作总和增加 2，奇偶性不变。

答案：不会改变。

练习 B

在黑白棋盘上，每次可把一个 2x2 小方块四格全部翻色（黑变白、白变黑）。问黑格总数的奇偶性是否不变？

点击查看过程与答案

一次操作中黑格数变化量可能为 $-4,-2,0,2,4$，均为偶数，故奇偶性不变。

答案：不变。

练习 C

数轴上从 0 出发，每次走 +4 或 -6。问能否到达 5？

点击查看过程与答案

位置恒为 $4x-6y=2(2x-3y)$，始终为偶数，不可能到达奇数 5。

答案：不能到达。

练习 D

9x9 棋盘删去一个黑格和一个白格，是否一定能被 1x2 骨牌覆盖？

点击查看过程与答案

黑白数量相等只是必要条件，不是充分条件；仍可能因形状割裂而无法覆盖。

答案：不一定。