排列組合中涂色問題的常見方法與策略

《排列組合中涂色問題的常見方法與策略》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、排列組合中涂色問題的常見方法及策略與涂色問題有關(guān)的試題新穎有趣,其中包含著豐富的數(shù)學(xué)思想。解決涂色問題方法技巧性強且靈活多變，故這類問題的利于培養(yǎng)學(xué)生的創(chuàng)新思維能力、分析問題與觀察問題的能力，有利于開發(fā)學(xué)生的智力。本專題總結(jié)涂色問題的常見類型及求解方法。一、區(qū)域涂色問題1、根據(jù)分步計數(shù)原理，對各個區(qū)域分步涂色，這是處理染色問題的基本方法。例1、用5種不同的顏色給圖中標(biāo)①、②、③、④的各部分涂色，每部分只涂一種顏色，相鄰部分涂不同顏色，則不同的涂色方法有多少種？②①③④分析：先給①號區(qū)域涂色有5種方法，再給②號涂色有4種方法，接著給③號涂色方法有3種，由于④號與①、

2、②不相鄰，因此④號有4種涂法，根據(jù)分步計數(shù)原理，不同的涂色方法有2、根據(jù)共用了多少種顏色討論，分別計算出各種出各種情形的種數(shù)，再用加法原理求出不同的涂色方法種數(shù)。例2、（2003江蘇卷）四種不同的顏色涂在如圖所示的6個區(qū)域，且相鄰兩個區(qū)域不能同色。①②2③④⑤⑥分析：依題意只能選用4種顏色，要分四類：（1）②與⑤同色、④與⑥同色，則有；（2）③與⑤同色、④與⑥同色，則有；（3）②與⑤同色、③與⑥同色，則有；（4）③與⑤同色、②與④同色，則有；（5）②與④同色、③與⑥同色，則有；所以根據(jù)加法原理得涂色方法總數(shù)為5=120例3、（2003年全國高考題）如圖所示，一個地

3、區(qū)分為5個行政區(qū)域，現(xiàn)給地圖著色，要求相鄰區(qū)域不得使用同一顏色，現(xiàn)有4種顏色可供選擇，則不同的著方法共有多少種？分析：依題意至少要用3種顏色243151)當(dāng)先用三種顏色時，區(qū)域2與4必須同色，2)區(qū)域3與5必須同色，故有種；3)當(dāng)用四種顏色時，若區(qū)域2與4同色，4)則區(qū)域3與5不同色，有種；若區(qū)域3與5同色，則區(qū)域2與4不同色，有種，故用四種顏色時共有2種。由加法原理可知滿足題意的著色方法共有+2=24+224=721、根據(jù)某兩個不相鄰區(qū)域是否同色分類討論，從某兩個不相鄰區(qū)域同色與不同色入手，分別計算出兩種情形的種數(shù)，再用加法原理求出不同涂色方法總數(shù)。例4用紅、黃

4、、藍、白、黑五種顏色涂在如圖所示的四個區(qū)域內(nèi)，每個區(qū)域涂一種顏色，相鄰兩個區(qū)域涂不同的顏色，如果顏色可以反復(fù)使用，共有多少種不同的涂色方法？1234分析：可把問題分為三類：（1）四格涂不同的顏色，方法種數(shù)為；（2）有且僅兩個區(qū)域相同的顏色，即只有一組對角小方格涂相同的顏色，涂法種數(shù)為；5)兩組對角小方格分別涂相同的顏色，涂法種數(shù)為，因此，所求的涂法種數(shù)為2、根據(jù)相間區(qū)使用顏色的種類分類ABCDEF例5如圖，6個扇形區(qū)域A、B、C、D、E、F，現(xiàn)給這6個區(qū)域著色，要求同一區(qū)域涂同一種顏色，相鄰的兩個區(qū)域不得使用同一種顏色，現(xiàn)有4種不同的顏色可供選擇解（1）當(dāng)相間區(qū)域

5、A、C、E著同一種顏色時，有4種著色方法，此時，B、D、F各有3種著色方法，此時，B、D、F各有3種著色方法故有種方法。（2）當(dāng)相間區(qū)域A、C、E著色兩不同的顏色時，有種著色方法，此時B、D、F有種著色方法，故共有種著色方法。（3）當(dāng)相間區(qū)域A、C、E著三種不同的顏色時有種著色方法，此時B、D、F各有2種著色方法。此時共有種方法。故總計有108+432+192=732種方法。說明：關(guān)于扇形區(qū)域區(qū)域涂色問題還可以用數(shù)列中的遞推公來解決。一、點的涂色問題方法有：（1）可根據(jù)共用了多少種顏色分類討論（2）根據(jù)相對頂點是否同色分類討論，（3）將空間問題平面化，轉(zhuǎn)化成區(qū)域涂

6、色問題。例6、將一個四棱錐的每個頂點染上一種顏色，并使同一條棱的兩端點異色，如果只有5種顏色可供使用，那么不同的染色方法的總數(shù)是多少？解法一：滿足題設(shè)條件的染色至少要用三種顏色。（1）若恰用三種顏色，可先從五種顏色中任選一種染頂點S，再從余下的四種顏色中任選兩種涂A、B、C、D四點，此時只能A與C、B與D分別同色，故有種方法。（2）若恰用四種顏色染色，可以先從五種顏色中任選一種顏色染頂點S，再從余下的四種顏色中任選兩種染A與B，由于A、B顏色可以交換，故有種染法；再從余下的兩種顏色中任選一種染D或C，而D與C，而D與C中另一個只需染與其相對頂點同色即可，故有種方法

7、。（3）若恰用五種顏色染色，有種染色法綜上所知，滿足題意的染色方法數(shù)為60+240+120=420種。解法二：設(shè)想染色按S—A—B—C—D的順序進行，對S、A、B染色，有種染色方法。由于C點的顏色可能與A同色或不同色，這影響到D點顏色的選取方法數(shù)，故分類討論：SCDABC與A同色時（此時C對顏色的選取方法唯一），D應(yīng)與A（C）、S不同色，有3種選擇；C與A不同色時，C有2種選擇的顏色，D也有2種顏色可供選擇，從而對C、D染色有種染色方法。由乘法原理，總的染色方法是解法三：可把這個問題轉(zhuǎn)化成相鄰區(qū)域不同色問題：如圖，對這五個區(qū)域用5種顏色涂色，有多少種不同的涂色方法

8、？解答略。