给定整数 $n\geqslant 2$．对平面直角坐标系中的整点集 $A=\{(a,b)~|~a,b\in\{1,2,\ldots,n\}\}$ 中的每个点染红，黄，蓝三种颜色之一，且满足：对任意 $a,b\in\{1,2,\ldots,n-1\}$，若 $(a,b)$ 与 $(a+1,b)$ 两点同色，则 $(a,b+1)$ 与 $(a+1,b+1)$ 两点亦同色．求不同的染色方式的总数．
【难度】
【出处】
2015中国东南数学奥林匹克试题(高二)
【标注】
【答案】
略
【解析】
对 $k=1,2,\ldots,n$，定义整点集 $A_k = \{(k,b)~|~b\in\{1,2,\ldots,n\}\}$．
我们对 $A_1 , A_2 , \ldots , A_n$ 依次进行染色（以完成对 $A$ 的染色）．
在这 $n$ 个步骤中，将对 $A$ 染色的方式数记为 $N_k$．（$k=1,2,\ldots ,n$）．
先对 $A_1$ 进行染色：因每个整点 $(1,b)$（$b=1,2,\ldots,n$）有 $3$ 种染法，故 $N_1 = 3^n$．
假定已染好 $A_1 \cup \ldots \cup A_r$，（$1\leqslant r\leqslant n-1$），下面对 $A_{r+1}$ 进行染色．
若对每个 $s=1,2,\ldots ,n$，均有 $(r+1,s)$ 与 $(r,s)$ 不同色，则 $A_{r+1}$ 的每个整点各有 $2$ 种染法，由乘法原理知，该情况下有 $2^n$ 种对 $A_{r+1}$ 的染法．
再考虑这样的情况：对于某个 $s$（$1\leqslant s\leqslant n$），
$(r+1,s)$ 与 $(r,s)$ 同色，但不存在小于 $s$ 的正整数 $u$，使得 $(r+1,u)$ 与 $(r,u)$ 同色．此时，$(r+1,u)$（$1\leqslant u\leqslant s-1$）这 $s-1$ 个方格各有 $2$ 种染法
（若 $s=1$，则没有方格需要染色，视为 $1$ 种染法）；注意到 $(r+1,s)$ 与 $(r,s)$ 同色，结合染色规则，依次可知 $(r+1,v)$ 与 $(r,v)$ 同色，其中 $v$ 依次取 $s+1,\ldots,n$．
根据乘法原理知，这种情況下有 $2^{s-1}$ 种对 $A_{r+1}$ 的染法．
综上可知，对 $A_{r+1}$ 染色的方式数为 $\displaystyle
N_{r+1}=2^{n}+\sum\limits_{s=1}^{n} 2^{s-1}=2^{n+1}-1
$．
由乘法原理知，对 $A$ 染色的方式数为 $
N_{1} N_{2} \ldots N_{n}=3^{n} \cdot\left(2^{n+1}-1\right)^{n-1}
$．
我们对 $A_1 , A_2 , \ldots , A_n$ 依次进行染色（以完成对 $A$ 的染色）．
在这 $n$ 个步骤中，将对 $A$ 染色的方式数记为 $N_k$．（$k=1,2,\ldots ,n$）．
先对 $A_1$ 进行染色：因每个整点 $(1,b)$（$b=1,2,\ldots,n$）有 $3$ 种染法，故 $N_1 = 3^n$．
假定已染好 $A_1 \cup \ldots \cup A_r$，（$1\leqslant r\leqslant n-1$），下面对 $A_{r+1}$ 进行染色．
若对每个 $s=1,2,\ldots ,n$，均有 $(r+1,s)$ 与 $(r,s)$ 不同色，则 $A_{r+1}$ 的每个整点各有 $2$ 种染法，由乘法原理知，该情况下有 $2^n$ 种对 $A_{r+1}$ 的染法．
再考虑这样的情况：对于某个 $s$（$1\leqslant s\leqslant n$），
$(r+1,s)$ 与 $(r,s)$ 同色，但不存在小于 $s$ 的正整数 $u$，使得 $(r+1,u)$ 与 $(r,u)$ 同色．此时，$(r+1,u)$（$1\leqslant u\leqslant s-1$）这 $s-1$ 个方格各有 $2$ 种染法
（若 $s=1$，则没有方格需要染色，视为 $1$ 种染法）；注意到 $(r+1,s)$ 与 $(r,s)$ 同色，结合染色规则，依次可知 $(r+1,v)$ 与 $(r,v)$ 同色，其中 $v$ 依次取 $s+1,\ldots,n$．
根据乘法原理知，这种情況下有 $2^{s-1}$ 种对 $A_{r+1}$ 的染法．
综上可知，对 $A_{r+1}$ 染色的方式数为 $\displaystyle
N_{r+1}=2^{n}+\sum\limits_{s=1}^{n} 2^{s-1}=2^{n+1}-1
$．
由乘法原理知，对 $A$ 染色的方式数为 $
N_{1} N_{2} \ldots N_{n}=3^{n} \cdot\left(2^{n+1}-1\right)^{n-1}
$．
答案
解析
备注
