染色与奇偶分析
核心概念
奇偶分析:关注一个量是奇还是偶。常用事实:
- 奇 奇 偶,偶 偶 偶,奇 偶 奇;
- 若某操作每次让某个量的奇偶性保持不变,则该奇偶性是一个不变量,可用来证明"某目标状态不可达"。
染色法:给棋盘、格点或对象按某种规则染色(常用黑白相间),把"覆盖、移动、配对"问题转化为"两种颜色的数量关系"。
核心思想——不变量:寻找一个在所有允许操作下都不改变的量(奇偶、颜色差、总和的余数等)。若初始与目标的这个量不同,则无论如何操作都到不了——这是证明不可能的利器。
直观理解 · 动手试试
很多问题问"能不能做到",直接尝试既费力又不可能穷尽。奇偶与染色提供了一条捷径:找一个操作改变不了的量。如果起点和终点在这个量上就不一样,那答案立刻是"不可能",一行论证胜过千百次尝试。
经典画面是国际象棋盘:每块多米诺骨牌不论横竖都恰好盖住一黑一白。所以无论怎么摆,被覆盖的黑格数永远等于白格数。一旦去掉两个同色格,黑白数量失衡,棋盘就再也不可能被完整覆盖——这就是染色不变量的力量。
缺角棋盘能否被多米诺铺满？
两个对角同色,去掉后深浅失衡。每张骨牌盖一深一浅,数量不等就永远铺不满——一行论证胜过万次尝试。
去掉 棋盘的两个对角(同为白色)的方格,问能否用 张 多米诺骨牌恰好覆盖剩下 格?
▸查看解答步骤
答: 不可能
桌上有 枚硬币全部正面朝上。每次必须同时翻转 枚。能否经过若干次操作使所有硬币都反面朝上?
▸查看解答步骤
答: 不可能全部变号
即时练习
去掉国际象棋盘两个对角方格后,可以用 张 骨牌完整覆盖剩余 格。
两对角同色,去掉后黑白失衡(32 与 30),而每张骨牌盖一黑一白,无法覆盖。
枚正面朝上的硬币,每次翻 枚,能全部变成反面朝上。
正面数初始为奇数 ,每次改变偶数张,奇偶性不变,到不了偶数 。
每张 骨牌在黑白相间的棋盘上覆盖的颜色情况是?
恰好一黑一白两格同色视摆放方向而定无法确定相邻两格颜色必不同,所以每张骨牌恰覆盖一黑一白。
若某操作每次都使一个整数改变偶数,则该整数的奇偶性永远不变。
加减偶数不改变奇偶性,所以它是一个不变量。
任取多少个整数,必有两个的个位数字相同?(填能保证的最少个数)
个位只有 共 种(抽屉),需 个。
枚正面朝上的硬币,每次翻 枚,能全部变成反面。
正面数初始为奇数 ,每次改变偶数张,奇偶性不变,到不了 。
易错点
- 染色规则选得不对。 染色方式要与问题的操作相匹配(常用黑白相间),错误的染色得不到有用的不变量。
- 把"找不到方法"当成"证明了不可能"。 试不出来不等于不存在;要靠不变量严格论证不可能。
- 不变量并非总存在。 奇偶/染色擅长证否,要证"可以做到"通常还得给出具体构造。