给定奇数 $n\geqslant 3$，用黑白两种颜色对 $ n\times n$ 方格表的每个格染色．称具有相同颜色且有公共顶点的两个格为”相邻的＂．对任意两个格 $a、b$，若存在一系列格 $c_{1}, c_{2}, \cdots, c_{k}$ 使得 $c_{1}=a, c_{k}=b, c_{i}(i=1,2, \cdots, k-1)$ 与 $c_{i+1}$ 相 邻，则称 $a$ 与 $b$ "连通”．求最大正整数 $M$，使得存在一种染色方案，其中有 $M$ 个两两不连通的格．
【难度】
【出处】
2017第33届CMO试题
【标注】
【答案】
略
【解析】
考虑推广的问题．
对 $m \times n$ 方格表黑白染色，其中，$m、n$ 均为不小于 $ 3$ 的奇数．在给定的染色方案下，所有的格可被划分成若干连通分支，使得同一个连通分支中的格彼此连通，不同连通分支中的格不连通．连通分支的数目记为 $K$．
下面用数学归纳法证明：
（1）$K \leqslant \frac{1}{4}(m+1)(n+1)+1$；
（2）当 $K=\frac{1}{4}(m+1)(n+1)+1$ 时，方格表四角处的每个格均不与其他格连通．
当 $m=n=3$ 时，最外一圈八个格至多属于四个与中心格异色的连通分支，故 $K\leqslant 5$．等号成立当且仅当四角处的方格与其他五个格异色．
接下来设 $m\geqslant 5$．记方格表的第 $2$ 行从左到右形成黑白交错的 $ k$ 段 $A_{1}, A_{2}, \cdots, A_{k}$ 各段的格数依次为 $x_{1}, x_{2}, \cdots, x_{k}$．设 $P$ 为含有第 $1$ 行格但不含第 $2$ 行格的连通分支数目．
记 $\lceil x\rceil$ 表示不小于实数 $x$ 的最小整数．下面估计 $P$．
若 $k\geqslant 2$，$A_1 $ 上面的 $x_1$ 个格中，最后一个格与 $ A_1$ 最后一个格以及 $A_2$ 的第一个格中有一个同色，从而，与第 $2$ 行的某个格连通；在前 $x_1-1$ 个格中至多有 $\left[\dfrac{x_{1}-1}{2}\right]$ 个格与 $A_1$ 异色，且互相不连通类似地，在 $A_k$ 上面的格中也至多有 $\left[\dfrac{x_{k}-1}{2}\right]$ 个格与第 $2$ 行的格不连通，且彼此也不连通．
对 $1< i < k$，$A_i$ 上面的格除第一个和最后一个格，中间 $x
_i-2$ 个格中，至多有 $\left\lceil\dfrac{x_{i}-2}{2}\right\rceil$ 个格与 $A_i$ 异色，且互相不连通．
故 $P \leqslant\left\lceil\dfrac{x_{1}-1}{2}\right\rceil+\left\lceil\dfrac{x_{k}-1}{2}\right\rceil+\sum_{i=2}^{k-1}\left\lceil\dfrac{x_{i}-2}{2}\right\rceil\leqslant \dfrac{n-k+2}{2}$．
若 $k=1$，则也有 $P \leqslant\left\lceil\dfrac{n}{2}\right\rceil=\dfrac{n-k+2}{2}$．
若 $k=1$，则也有 $P \leqslant\left\lceil\dfrac{n}{2}\right\rceil=\dfrac{n-k+2}{2}$．
设 $Q$ 为含有第 $2$ 行格但不含第 $3$ 行格的连通分支数目．由于 $A_i$ 和 $A_{i+1}$ 中总有一段与第三行中的格连通（考虑 $A_i$ 最后一个格和 $A_{i+1}$ 的第一个格，它们异色，其中一个必与第三行的格连通），故 $Q \leqslant\left\lceil\dfrac{k}{2} \right\rceil \leqslant \dfrac{k+1}{2}$．
设 $R$ 为含有第 $3$ 至 $m$ 行格的连通分支 数目．
由归纳假设（1）知 $R \leqslant \dfrac{1}{4}(m-1)(n+1)+1$．
下面证明：若 $Q=\dfrac{k+1}{2}$（$k$ 为奇数）或 $Q=\dfrac{k}{2}$（$k$ 为偶数），则 $R \leqslant \dfrac{1}{4}(m-1)(n+1)$．
事实上，当 $k$ 为奇数，且 $Q=\dfrac{k+1}{2}$ 时，若 $k= 1$．则 $Q= 1$，第 $2$ 行所有的格同色，第 $3$ 行 所有的格也同色．
由归纳假设（2）知 $R \leqslant \dfrac{1}{4}(m-1)(n+1)$．
若奇数 $k\geqslant 3$，设 $A_i$ 下面的格为 $B_i$，由于 $A_{1}, A_{3}, \cdots, A_{k}$ 均不与第3行的格连通，故 $B_{1},B_{3}, \cdots, B_{k}$ 与 $A_{1}, A_{3}, \cdots, A_{k}$ 异色．于是，与 $A_2,A_{4}, \cdots, A_{k-1}$ 同色．从而，$B_{1}, A_{2}, B_{3}, A_{4}, B_{5}, \cdots,A_{k-1}, B_{k}$ 均连通．
由归纳假设（2）知 $R \leqslant \dfrac{1}{4}(m-1)(n+1)$．
当 $k$ 为偶数，且 $Q=\dfrac{k}{2}$ 时，若 $R=\dfrac{1}{4}(m-1)(n+1)+1$，则由归纳假设（2），知第 $3$ 行第一个格与第二个格异色，这祥，$A_1$ 与第 $3$ 行的格连通类似地，$A_k$ 也与第 $3$ 行的格连通．由此，在 $A_2,A_3,\cdots,A_{k-1}$ 中，至多只有 $\dfrac{k-2}{2}$ 段与的格不连通故第 $3$ 行中的格不连通．故 $Q \leqslant \dfrac{k-2}{2}$，这与 $Q=\dfrac{k}{2}$ 的假设矛盾．
因此，当 $Q=\dfrac{k+1}{2}$ 或 $Q=\dfrac{k}{2}$ 时，有 $R \leqslant \dfrac{1}{4}(m-1)(n+1)$．
则 $K=P+Q+R\leqslant \dfrac{n-k+2}{2}+\dfrac{k+1}{2}+\dfrac{1}{4}(m-1)(n+1)=\dfrac{1}{4}(m+1)(n+1)+1$
当等号成立时，必须 $k$ 为奇数，且 $P=\dfrac{n-k+2}{2}$．
考虑 $P$ 的估计中等号成立的条件，知第 $1$ 行第一个格与最后一个格分别被三个异色 格包围．由方格表的对称性，知四角处的每个格均不与其他格连通．
由方格表的对称性，知四角处的每个格均不与其他格连通．
容易验证，对于第 $i$ 行 $j$ 列的格，若 $ij$ 为偶数将其染成黑色；若 $ij$ 为奇数，将其染成白色．在此两种染色方案下，均有 $K=\dfrac{1}{4}(m+1)(n+1)+1$．
综上，所求 $M=\dfrac{1}{4}(n+1)^{2}+1$．
对 $m \times n$ 方格表黑白染色，其中，$m、n$ 均为不小于 $ 3$ 的奇数．在给定的染色方案下，所有的格可被划分成若干连通分支，使得同一个连通分支中的格彼此连通，不同连通分支中的格不连通．连通分支的数目记为 $K$．
下面用数学归纳法证明：
（1）$K \leqslant \frac{1}{4}(m+1)(n+1)+1$；
（2）当 $K=\frac{1}{4}(m+1)(n+1)+1$ 时，方格表四角处的每个格均不与其他格连通．
当 $m=n=3$ 时，最外一圈八个格至多属于四个与中心格异色的连通分支，故 $K\leqslant 5$．等号成立当且仅当四角处的方格与其他五个格异色．
接下来设 $m\geqslant 5$．记方格表的第 $2$ 行从左到右形成黑白交错的 $ k$ 段 $A_{1}, A_{2}, \cdots, A_{k}$ 各段的格数依次为 $x_{1}, x_{2}, \cdots, x_{k}$．设 $P$ 为含有第 $1$ 行格但不含第 $2$ 行格的连通分支数目．
记 $\lceil x\rceil$ 表示不小于实数 $x$ 的最小整数．下面估计 $P$．
若 $k\geqslant 2$，$A_1 $ 上面的 $x_1$ 个格中，最后一个格与 $ A_1$ 最后一个格以及 $A_2$ 的第一个格中有一个同色，从而，与第 $2$ 行的某个格连通；在前 $x_1-1$ 个格中至多有 $\left[\dfrac{x_{1}-1}{2}\right]$ 个格与 $A_1$ 异色，且互相不连通类似地，在 $A_k$ 上面的格中也至多有 $\left[\dfrac{x_{k}-1}{2}\right]$ 个格与第 $2$ 行的格不连通，且彼此也不连通．
对 $1< i < k$，$A_i$ 上面的格除第一个和最后一个格，中间 $x
_i-2$ 个格中，至多有 $\left\lceil\dfrac{x_{i}-2}{2}\right\rceil$ 个格与 $A_i$ 异色，且互相不连通．
故 $P \leqslant\left\lceil\dfrac{x_{1}-1}{2}\right\rceil+\left\lceil\dfrac{x_{k}-1}{2}\right\rceil+\sum_{i=2}^{k-1}\left\lceil\dfrac{x_{i}-2}{2}\right\rceil\leqslant \dfrac{n-k+2}{2}$．
若 $k=1$，则也有 $P \leqslant\left\lceil\dfrac{n}{2}\right\rceil=\dfrac{n-k+2}{2}$．
若 $k=1$，则也有 $P \leqslant\left\lceil\dfrac{n}{2}\right\rceil=\dfrac{n-k+2}{2}$．
设 $Q$ 为含有第 $2$ 行格但不含第 $3$ 行格的连通分支数目．由于 $A_i$ 和 $A_{i+1}$ 中总有一段与第三行中的格连通（考虑 $A_i$ 最后一个格和 $A_{i+1}$ 的第一个格，它们异色，其中一个必与第三行的格连通），故 $Q \leqslant\left\lceil\dfrac{k}{2} \right\rceil \leqslant \dfrac{k+1}{2}$．
设 $R$ 为含有第 $3$ 至 $m$ 行格的连通分支 数目．
由归纳假设（1）知 $R \leqslant \dfrac{1}{4}(m-1)(n+1)+1$．
下面证明：若 $Q=\dfrac{k+1}{2}$（$k$ 为奇数）或 $Q=\dfrac{k}{2}$（$k$ 为偶数），则 $R \leqslant \dfrac{1}{4}(m-1)(n+1)$．
事实上，当 $k$ 为奇数，且 $Q=\dfrac{k+1}{2}$ 时，若 $k= 1$．则 $Q= 1$，第 $2$ 行所有的格同色，第 $3$ 行 所有的格也同色．
由归纳假设（2）知 $R \leqslant \dfrac{1}{4}(m-1)(n+1)$．
若奇数 $k\geqslant 3$，设 $A_i$ 下面的格为 $B_i$，由于 $A_{1}, A_{3}, \cdots, A_{k}$ 均不与第3行的格连通，故 $B_{1},B_{3}, \cdots, B_{k}$ 与 $A_{1}, A_{3}, \cdots, A_{k}$ 异色．于是，与 $A_2,A_{4}, \cdots, A_{k-1}$ 同色．从而，$B_{1}, A_{2}, B_{3}, A_{4}, B_{5}, \cdots,A_{k-1}, B_{k}$ 均连通．
由归纳假设（2）知 $R \leqslant \dfrac{1}{4}(m-1)(n+1)$．
当 $k$ 为偶数，且 $Q=\dfrac{k}{2}$ 时，若 $R=\dfrac{1}{4}(m-1)(n+1)+1$，则由归纳假设（2），知第 $3$ 行第一个格与第二个格异色，这祥，$A_1$ 与第 $3$ 行的格连通类似地，$A_k$ 也与第 $3$ 行的格连通．由此，在 $A_2,A_3,\cdots,A_{k-1}$ 中，至多只有 $\dfrac{k-2}{2}$ 段与的格不连通故第 $3$ 行中的格不连通．故 $Q \leqslant \dfrac{k-2}{2}$，这与 $Q=\dfrac{k}{2}$ 的假设矛盾．
因此，当 $Q=\dfrac{k+1}{2}$ 或 $Q=\dfrac{k}{2}$ 时，有 $R \leqslant \dfrac{1}{4}(m-1)(n+1)$．
则 $K=P+Q+R\leqslant \dfrac{n-k+2}{2}+\dfrac{k+1}{2}+\dfrac{1}{4}(m-1)(n+1)=\dfrac{1}{4}(m+1)(n+1)+1$
当等号成立时，必须 $k$ 为奇数，且 $P=\dfrac{n-k+2}{2}$．
考虑 $P$ 的估计中等号成立的条件，知第 $1$ 行第一个格与最后一个格分别被三个异色 格包围．由方格表的对称性，知四角处的每个格均不与其他格连通．
由方格表的对称性，知四角处的每个格均不与其他格连通．
容易验证，对于第 $i$ 行 $j$ 列的格，若 $ij$ 为偶数将其染成黑色；若 $ij$ 为奇数，将其染成白色．在此两种染色方案下，均有 $K=\dfrac{1}{4}(m+1)(n+1)+1$．
综上，所求 $M=\dfrac{1}{4}(n+1)^{2}+1$．
答案
解析
备注
