Question

6．設(shè)正整數(shù)n≥2，對(duì)2×n格點(diǎn)鏈中的2n個(gè)結(jié)點(diǎn)用紅（R）、黃（Y）、藍(lán)（B）三種顏色染色，左右端點(diǎn)中的三個(gè)結(jié)點(diǎn)己經(jīng)染好色，如圖所示．若對(duì)剩余的2n-3個(gè)結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)恰染-種顏色，相鄰結(jié)點(diǎn)異色，求不同的染色方法數(shù)．

Answer 1

分析 需要分類討論，記P=R（或Y），Q=B時(shí)的著色數(shù)目為a_n，記P=B，Q=R（或Y）時(shí)的著色數(shù)目為b_n，記P=R，Q=Y或者P=Y，Q=R時(shí)的著色數(shù)目為c_n，根據(jù)端點(diǎn)的個(gè)數(shù)不同，分別求出找到相應(yīng)的規(guī)律，即可得到a_n=2b_n-1+c_n-1=a_n-1+b_n-1+c_n-1=3^n-2，問題得以解決．

解答 解：2×n格點(diǎn)鏈中的2n個(gè)結(jié)點(diǎn)用紅（R）、黃（Y）、藍(lán)（B）三種顏色染色，其中最左端點(diǎn)染成紅色與黃色，設(shè)右端點(diǎn)染色為P，Q，如圖所示：

記P=R（或Y），Q=B時(shí)的著色數(shù)目為a_n，
記P=B，Q=R（或Y）時(shí)的著色數(shù)目為b_n，
記P=R，Q=Y或者P=Y，Q=R時(shí)的著色數(shù)目為c_n，
我們注意到：（1）若右端沒有約束時(shí)，每增加一個(gè)格子都有3種不同的著色方法，則a_n+b_n+c_n=3^n-1，
（2）由對(duì)稱性，即將圖形山下翻轉(zhuǎn)，并且顏色R與Y互換，可知a_n=b_n，
（3）考慮相互的遞推特征，如圖：則a_n=2b_n-1+c_n-1，

所以，$\left\{\begin{array}{l}{{a}_{n}+_{n}+{c}_{n}={3}^{n-1}}\\{{a}_{n}=_{n}}\\{{a}_{n}=2_{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，
即為問題所求的不同的染色方法數(shù)．

點(diǎn)評(píng) 本題考查了著色問題，關(guān)鍵是需要分類討論，以及找到相應(yīng)的規(guī)律，屬于難題．