染色问题

染色问题分两类：

• 证明不可能：给对象规定一种染色（往往只有两种颜色），用奇偶或抽屉说明题目要求的状态碰不上这种染色，从而不可能；
• 构造可能：给出一种具体的染色方案或操作序列，展示可以达到。

黑白二染色是最常用的：国际象棋盘相邻格异色、坐标 $(x,y)$ 按 $x+y$ 奇偶染色，都是把几何问题翻译成奇偶问题的桥梁。

• 棋盘去角：$8\times 8$ 棋盘去掉对角两格后，无法用 $31$ 个 $1\times 2$ 骨牌铺满——黑白染色后黑白格数不等，而每个骨牌恰盖一黑一白。
• 路径染色：相邻区域染不同色的可行性问题，与图的最短路奇偶相关。

操作与游戏类染色题的内核是不变量：染色后，每个操作对“黑格上棋子数减白格上棋子数”这类量的改变是固定的（比如不变、或变固定值），于是终点状态的该量被锁定，达不到就说明不可能。

例1 骨牌铺棋盘

$8\times 8$ 棋盘去掉左上、右下两个角格，能否用 $31$ 个 $1\times 2$ 骨牌完全覆盖？

解：按国际象棋盘方式染色，相邻格异色。左上角与右下角同色（$8\times 8$ 中 $(1,1)$ 与 $(8,8)$ 的 $x+y$ 都是偶数）。

原棋盘黑白各 $32$ 格，去掉两个同色格后，一色 $30$ 格、另一色 $32$ 格。

每个骨牌无论横放竖放都盖住一黑一白，$31$ 个骨牌只能盖黑白各 $31$ 格，与 $30/32$ 的分布不符，所以不可能。

例2 换角再问

$8\times 8$ 棋盘去掉左上、右上两个角格，能否用 $31$ 个 $1\times 2$ 骨牌覆盖？

解：$(1,1)$ 与 $(1,8)$ 的 $x+y$ 一奇一偶，去掉的两格异色，剩下黑白各 $30$ 格，染色障碍消失。

染色挡不住时回到构造：第一行去掉两角后剩 $6$ 格，用 $3$ 个横骨牌盖住；其余 $7$ 行每行 $8$ 格用 $4$ 个横骨牌盖住，共 $3+28=31$ 个，可以覆盖。

顺序值得记住：染色证不可能，构造证可能，两步走完整才算回答了覆盖问题。

例3 直线分平面加抽屉

平面上 $5$ 个点，任意三点不共线。证明其中存在 $4$ 个点构成凸四边形。

解：先看 $5$ 点的凸包。若凸包至少有 $4$ 个顶点，这 $4$ 个顶点就是凸四边形，结论成立。

剩下凸包为三角形的情形：设三角形为 $ABC$，另外两点 $P$、$Q$ 在其内部。直线 $PQ$ 把平面分成两个半平面，$A$、$B$、$C$ 三点落入两侧，由抽屉原理必有两点在同一侧，设为 $A$、$B$。

于是线段 $AB$ 与线段 $PQ$ 分居直线两侧、互不相交，端点错开，四点 $A$、$P$、$B$、$Q$ 构成凸四边形。

这道题与二染色同属一个思想：先用一个二元划分（直线的两侧）把配置切成两类，再用抽屉逼出想要的组合。