Question

6．设正整数n≥2，对2×n格点链中的2n个结点用红（R）、黄（Y）、蓝（B）三种颜色染色，左右端点中的三个结点己经染好色，如图所示．若对剩余的2n-3个结点，要求每个结点恰染-种颜色，相邻结点异色，求不同的染色方法数．

Answer 1

分析 需要分类讨论，记P=R（或Y），Q=B时的着色数目为a_n，记P=B，Q=R（或Y）时的着色数目为b_n，记P=R，Q=Y或者P=Y，Q=R时的着色数目为c_n，根据端点的个数不同，分别求出找到相应的规律，即可得到a_n=2b_n-1+c_n-1=a_n-1+b_n-1+c_n-1=3^n-2，问题得以解决．

解答 解：2×n格点链中的2n个结点用红（R）、黄（Y）、蓝（B）三种颜色染色，其中最左端点染成红色与黄色，设右端点染色为P，Q，如图所示：

记P=R（或Y），Q=B时的着色数目为a_n，
记P=B，Q=R（或Y）时的着色数目为b_n，
记P=R，Q=Y或者P=Y，Q=R时的着色数目为c_n，
我们注意到：（1）若右端没有约束时，每增加一个格子都有3种不同的着色方法，则a_n+b_n+c_n=3^n-1，
（2）由对称性，即将图形山下翻转，并且颜色R与Y互换，可知a_n=b_n，
（3）考虑相互的递推特征，如图：则a_n=2b_n-1+c_n-1，

所以，$\left\{\begin{array}{l}{{a}_{n}+{b}_{n}+{c}_{n}={3}^{n-1}}\\{{a}_{n}={b}_{n}}\\{{a}_{n}=2{b}_{n-1}+{c}_{n-1}}\end{array}\right.，n∈N*$
这样a_n=2b_n-1+c_n-1=a_n-1+b_n-1+c_n-1=3^n-2，
即为问题所求的不同的染色方法数．

点评 本题考查了着色问题，关键是需要分类讨论，以及找到相应的规律，属于难题．