涂色問題的常見解法及策略

■江蘇省鹽城市時楊中學 劉長柏

對于涂色問題的解法,撥云破霧、還其本來面目,就會發(fā)現(xiàn)實質(zhì)是用分類或分步計數(shù)原理導航,通過深入縝密分析題意,將原題化歸為熟悉的排列、組合或綜合題型,逐類分步推理求解的。涂色問題的常見解法：根據(jù)分步計數(shù)原理,對各個區(qū)域分步涂色;根據(jù)共用了多少顏色分類討論;根據(jù)不相鄰區(qū)域是否同色分類討論等。

一、根據(jù)分步計數(shù)原理，對各個區(qū)域分步涂色

例1用紅黃綠三種顏色給圖1中的5個帶狀格子涂色。要求每格涂一種顏色且相鄰格子不能涂同一種顏色,共有多少種不同的涂法?

圖1

分析：根據(jù)分步計數(shù)原理,對各個區(qū)域分步涂色,這是處理染色問題的基本方法。

解：從滿足一格一顏色、鄰格不同色的限制條件入手,分成三類：

練習1：用5種不同的顏色給圖2中標①、②、③、④的各部分涂色,每部分只涂一種顏色,相鄰部分涂不同顏色,則不同的涂色方法有多少種?

圖2

解：先給①號區(qū)域涂色有5種方法,再給②號涂色有4種方法,接著給③號涂色方法有3種,由于④號與①、②不相鄰,因此④號有4種涂法,根據(jù)分步計數(shù)原理,不同的涂色方法有5×4×3×4=240(種)。

二、根據(jù)共用了多少顏色分類討論

例2如圖3所示,花壇內(nèi)有5個花池,有5種不同顏色的花卉可供栽種,每個花池內(nèi)只能栽種同顏色的花卉,相鄰兩池的花卉顏色不同,則最多有多少種栽種方案?

分析：本題要完成的事件是花池內(nèi)栽種花卉;由于5種不同顏色的花卉可供選擇,所以可選擇3種、4種、5種不同顏色的花卉栽種,可見有3類方法可獨立完成這件事,而每一類又不能“一次性”完成,所以分步進行。

解：由題意知,最少用三種顏色的花卉,按照花卉選種的顏色可分為三種方案,即用三種顏色、四種顏色、五種顏色。

①當用三種顏色時,花池2、4栽同種顏色的花卉,有5種方案,花池3、5栽同種顏色的花卉,有4種方案,花池1有3種栽種方案,由分步計數(shù)原理知5×4×3=60(種)方案。

②當用四種顏色時,則花池2、4栽同種顏色的花卉或花池3、5栽同種顏色的花卉。若花池2、4栽同種顏色的花卉,則花池2、4有5種方案,花池3有4種栽種方案,花池5有3種栽種方案,花池1有2種栽種方案,由分步計數(shù)原理得5×4×3×2=120(種)栽種方案;若花池3、5栽同種顏色的花卉,同理得有5×4×3×2=120(種)栽種方案;再由分類計數(shù)原理得共有120+120=240(種)栽種方案。

圖3

③當用五種顏色時,花池1有5種栽種方案,花池2有4種栽種方案,花池3有3種栽種方案,花池4有2種栽種方案,花池5有1種栽種方案,由分步計數(shù)原理得5×4×3×2×1=120(種)栽種方案。

根據(jù)分類計數(shù)原理得60+240+120=420(種)栽種方案。

點評：對于一些較復(fù)雜的題目,往往既要分類又要分步,也就是說既要應(yīng)用分類加法計數(shù)原理又要運用分步乘法計數(shù)原理,在計數(shù)時應(yīng)讓兩個原理協(xié)同作用。當兩個原理混合使用時,一般是先分類再分步,在每類中再分步。

練習2：將一個四棱錐S-ABCD的每個頂點染上一種顏色,并使同一條棱的兩端點異色,如果只有5種顏色可供使用,那么不同的染色方法的總數(shù)是多少?

解：滿足題設(shè)條件的染色至少要用三種顏色。

(1)若恰用三種顏色,可先從五種顏色中任選一種染頂點S,再從余下的四種顏色中任選兩種涂A、B、C、D四點,此時只能A與C、B與D分別同色,故有CA=60(種)方法。

(2)若恰用四種顏色染色,可以先從五種顏色中任選一種顏色染頂點S,再從余下的四種顏色中任選兩種染A與B,由于A、B顏色可以交換,故有A種染法;再從余下的兩種顏色中任選一種染D或C,而D與C中另一個只需染與其相對頂點同色即可,故有CACC=240(種)方法。

綜上所知,滿足題意的染色方法數(shù)為60+240+120=420(種)。

三、根據(jù)不相鄰區(qū)域是否同色分類討論

例3用紅、黃、藍、白四種顏色涂矩形ABCD的四條邊,每條邊只涂一種顏色,且使相鄰兩邊涂不同的顏色,如果顏色可以反復(fù)使用,共有多少種不同的涂色方法?

分析：涂色按AB→BC→CD→DA的順序進行,對AB、BC涂色有4×3=12種涂色方法。由于CD的顏色可能與AB同色或不同色,這影響到DA顏色的選取方法數(shù),故分類討論。

解：當CD與AB同色時,這時CD對顏色的選取方法唯一,則DA有3種顏色可供選擇;當CD與AB不同色時,CD有兩種可供選擇的顏色,DA也有兩種可供選擇的顏色。從而對CD、DA涂色有1×3+2×2=7(種)涂色方法。

由乘法原理得,總的涂色方法數(shù)為12×7=84(種)。

點評：根據(jù)某兩個不相鄰區(qū)域是否同色分類討論,從某兩個不相鄰區(qū)域同色與不同色入手,分別計算出兩種情形的種數(shù),再用加法原理求出不同涂色方法總數(shù)。

四、涂色問題中的轉(zhuǎn)化

例4已知四棱錐P-ABCD,如圖4,用4種不同的顏色涂在四棱錐的各個面上,要求相鄰不同色,有多少種涂法?

圖4

圖5

分析：如圖5,區(qū)域1、2、3、4相當于四個側(cè)面,區(qū)域5相當于底面,進而根據(jù)共用顏色多少種分類討論。

解：如圖5,區(qū)域1、2、3、4相當于四個側(cè)面,區(qū)域5相當于底面。根據(jù)共用顏色多少種分類：

(1)最少要用3種顏色,即1與3同色、2與4同色,此時有A種方法;

(2)當用4種顏色時,1與3、2與4兩組中只能有一組同色,此時有CA種涂法。

點評：這種面的涂色問題可轉(zhuǎn)化為區(qū)域涂色問題,再利用區(qū)域的涂色方法進行求解。

練習3：直線x=m,y=x將圓面x2+y2≤4分成若干塊,現(xiàn)用5種顏色給這若干塊涂色,每塊只涂一種顏色,且任意兩塊不同色,共有120種涂法,則m的取值范圍是( )。

圖6

解：如圖6,①當m≤-2或m≥2時,圓面x2+y2≤4被分成2塊,涂色方法有20種;②當＜2時,圓面x2+y2≤4被分成3塊,涂色方法有60種;③當時,圓面x2+y2≤4被分成4塊,涂色方法有120種。所以m的取值范圍是,故選A。