將問題中的對象適當進行染色，有利於我們觀察、分析對象之間的關系。像國際象棋的棋盤那樣，我們可以把被研究的對象染上不同的顏色，許多隱藏的關系會變得明朗，再通過對染色圖形的處理達到對原問題的解決，這種解題方法稱為染色法。常見的染色方式有：點染色、線段染色、小方格染色和對區域染色。
例1 用15個“T”字形紙片和1個“田”字形紙片（如下圖所示），能否覆蓋壹個8×8的棋盤？
解：如下圖，將 8×8的棋盤染成黑白相間的形狀。如果15個“T”字形紙片和1個“田”字形紙片能夠覆蓋壹個8×8的棋盤，那麽它們覆蓋住的白格數和黑格數都應該是32個，但是每個“T”字形紙片只能覆蓋1個或3個白格，而1和3都是奇數，因此15個“T”字形紙片覆蓋的白格數是壹個奇數；又每個“田”字形紙片壹定覆蓋2個白格，從而15個“T”字形紙片與1個“田”字形紙片所覆蓋的白格數是奇數，這與32是偶數矛盾，因此，用它們不能覆蓋整個棋盤。
例2 如左下圖，把正方體分割成27個相等的小正方體，在中心的那個小正方體中有壹只甲蟲，甲蟲能從每個小正方體走到與這個正方體相鄰的6個小正方體中的任何壹個中去。如果要求甲蟲只能走到每個小正方體壹次，那麽甲蟲能走遍所有的正方體嗎？
解：甲蟲不能走遍所有的正方體。我們如右上圖將正方體分割成27個小正方體，塗上黑白相間的兩種顏色，使得中心的小正方體染成白色，再使兩個相鄰的小正方體染上不同的顏色。顯然，在27個小正方體中，14個是黑的，13個是白的。甲蟲從中間的白色小正方體出發，每走壹步，方格就改變壹種顏色。故它走27步，應該經過14個白色的小正方體、13個黑色的小正方體。因此在27步中至少有壹個小正方體，甲蟲進去過兩次。由此可見，如果要求甲蟲到每壹個小正方體只去壹次，那麽甲蟲不能走遍所有的小正方體。
例3 8×8的國際象棋棋盤能不能被剪成7個2×2的正方形和9個4×1的長方形？如果可以，請給出壹種剪法；如果不行，請說明理由。
解：如下圖，對8×8的棋盤染色，則每壹個4×1的長方形能蓋住2白2黑小方格，每壹個2×2的正方形能蓋住1白3黑或3白1黑小方格。推知7個正方形蓋住的黑格總數是壹個奇數，但圖中的黑格數為32，是壹個偶數，故這種剪法是不存在的。
例4 在平面上有壹個27×27的方格棋盤，在棋盤的正中間擺好81枚棋子，它們被擺成壹個9×9的正方形。按下面的規則進行遊戲：每壹枚棋子都可沿水平方向或豎直方向越過相鄰的棋子，放進緊挨著這枚棋子的空格中，並把越過的這枚棋子取出來。問：是否存在壹種走法，使棋盤上最後恰好剩下壹枚棋子？
解：如下圖，將整個棋盤的每壹格都分別染上紅、白、黑三種顏色，這種染色方式將棋盤按顏色分成了三個部分。按照遊戲規則，每走壹步，有兩部分中的棋子數各減少了壹個，而第三部分的棋子數增加了壹個。這表明每走壹步，每個部分的棋子數的奇偶性都要改變。
因為壹開始時，81個棋子擺成壹個9×9的正方形，顯然三個部分的棋子數是相同的，故每走壹步，三部分中的棋子數的奇偶性是壹致的。
如果在走了若幹步以後，棋盤上恰好剩下壹枚棋子，則兩部分上的棋子數為偶數，而另壹部分的棋子數為奇數，這種結局是不可能的，即不存在壹種走法，使棋盤上最後恰好剩下壹枚棋子。
例5 圖1是由數字0，1交替構成的，圖2是由圖1中任選 減1，如此反復多次形成的。問：圖2中的A格上的數字是多少？
解：如左下圖所示，將8×8方格黑白交替地染色。
此題允許右上圖所示的6個操作，這6個操作無論實行在哪個位置上，白格中的數字之和減去黑格中的數字之和總是常數。所以圖1中白格中的數字之和減去黑格中的數字之和，與圖2中白格中的數字之和減去黑格中的數字之和相等，都等於32，由（31＋A）-32=32，得出A=33。
例6 有壹批商品，每件都是長方體形狀，尺寸是1×2×4。現在有壹批現成的木箱，內空尺寸是6×6×6。問：能不能用這些商品將木箱填滿？
解：我們用染色法來解決這個問題。先將6×6×6的木箱分成216個小正方體，這216個小正方體，可以組成27個棱長為2的正方體。我們將這些棱長為2的正方體按黑白相間塗上顏色（如下圖）。
容易計算出，有14個黑色的，有13個白色的。現在將商品放入木箱內，不管怎麽放，每件商品要占據8個棱長為1的小正方體的空間，而且其中黑、白色的必須各占據4個。現在白色的小正方體***有8×13=104（個），再配上104個黑色的小正方體，壹***可以放26件商品，這時木箱余下的是8個黑色小正方體所占據的空間。這8個黑色的小正方體的體積雖然與壹件商品的體積相等，但是容不下這件商品。因此不能用這些商品剛好填滿。
例7 6個人參加壹個集會，每兩個人或者互相認識或者互相不認識。證明：存在兩個“三人組”，在每壹個“三人組”中的三個人，或者互相認識，或者互相不認識（這兩個“三人組”可以有公***成員）。
證明：將每個人用壹個點表示，如果兩人認識就在相應的兩個點之間連壹條紅色線段，否則就連壹條藍色線段。本題即是要證明在所得的圖中存在兩個同色的三角形。
設這六個點為A，B，C，D，E，F。我們先證明存在壹個同色的三角形：
考慮由A點引出的五條線段AB，AC，AD，AE，AF，其中必然有三條被染成了相同的顏色，不妨設AB，AC，AD同為紅色。再考慮△BCD的三邊：若其中有壹條是紅色，則存在壹個紅色三角形；若這三條都不是紅色，則存在壹個藍色三角形。
下面再來證明有兩個同色三角形：不妨設△ABC的三條邊都是紅色的。若△DEF也是三邊同為紅色的，則顯然就有兩個同色三角形；若△DEF三邊中有壹條邊為藍色，設其為DE，再考慮DA，DB，DC三條線段：若其中有兩條為紅色，則顯然有壹個紅色三角形；若其中有兩條是藍色的，則設其為DA，DB。此時在EA，EB中若有壹邊為藍色，則存在壹個藍色三角形；而若兩邊都是紅色，則又存在壹個紅色三角形。
故不論如何塗色，總可以找到兩個同色的三角形。
二、賦值法
將問題中的某些對象用適當的數表示之後，再進行運算、推理、解題的方法叫做賦值法。許多組合問題和非傳統的數論問題常用此法求解。常見的賦值方式有：對點賦值、對線段賦值、對區域賦值及對其他對象賦值。
例8 壹群旅遊者，從A村走到B村，路線如下圖所示。怎樣走才能在最短時間內到達B村？圖中的數字表示走這壹段路程需要的時間（單位：分）。
解：我們先把從A村到各村的最短時間標註在各村的旁邊，從左到右，壹壹標註，如下圖所示。
由此不難看出，按圖中的粗黑線走就能在最短時間（60分鐘）內從A村走到B村。
例9 把下圖中的圓圈任意塗上紅色或藍色。問：有無可能使得在同壹條直線上的紅圈數都是奇數？請說明理由。
解：假設題中所設想的染色方案能夠實現，那麽每條直線上代表各點的數字之和便應都是奇數。壹***有五條直線，把這五條直線上代表各點的數字之和的這五個奇數再加起來，得到的總和數仍應是壹個奇數。但是，由觀察可見，圖中每個點都恰好同時位於兩條直線上，在求上述總和數時，代表各點的數字都恰被加過兩次，所以這個總和應是壹個偶數。這就導致矛盾，說明假設不成立，染色方案不能實現。
例10 平面上n（n≥2）個點A1，A2，…，An順次排在同壹條直線上，每點塗上黑白兩色中的某壹種顏色。已知A1和An塗上的顏色不同。證明：相鄰兩點間連接的線段中，其兩端點不同色的線段的條數必為奇數。
證明：賦予黑點以整數值1，白點以整數值2，點Ai以整數
值為ai，當Ai為黑點時，ai=1，當Ai為白點時，ai=2。再賦予線段AiAi+1以整數值ai+ai+1，則兩端同色的線段具有的整數值為2或4，兩端異色的線段具有的整數值為3。
所有線段對應的整數值的總和為
（a1＋a2）＋（a2＋a3）＋（a3＋a4）＋…＋（an-1＋an）
＝a1＋an＋2（a2＋a3＋…＋an-1）
＝2＋1＋2（a2＋a3＋…＋an-1）＝奇數。
設具有整數值2，3，4的線段的條數依次為l，m，n，則
2l＋m＋4n=奇數。
由上式推知，m必為奇數，證明完畢。
例11 下面的表1是壹個電子顯示盤，每壹次操作可以使某壹行四個字母同時改變，或者使某壹列四個字母同時改變。改變的規則是按照英文字母的順序，每個英文字母變成它的下壹個字母（即A變成B，B變成C……Z變成A）。問：能否經過若幹次操作，使表1變為表2？如果能，請寫出變化過程，如果不能，請說明理由。
S O B R K B D S
T Z F P H E X G
H O C N R T B S
A D V X C F Y A
表1 表2
解：不能。將表中的英文字母分別用它們在字母表中的序號代替（即A用1，B用2……Z用26代替）。這樣表1和表2就分別變成了表3和表4。
每壹次操作中字母的置換相當於下面的置換：
1→2，2→3，…，25→26，26→1。
19 15 2 18
20 26 6 16
8 15 3 14
1 4 22 24
表3
11 2 4 19
8 5 24 7
18 20 2 19
3 6 25 1
表4
容易看出，每次操作使四個數字改變了奇偶性，而16個數字的和的奇偶性沒有改變。因為表3中16個數字的和為213，表4中16個數字的和為174，它們的奇偶性不同，所以表3不能變成表4，即表1不能變成表2。
例12 如圖（1）～（6）所示的六種圖形拼成右下圖，如果圖（1）必須放在右下圖的中間壹列，應如何拼？
解：把右上圖黑、白相間染色（見上圖）。其中有11個白格和10個黑格，當圖形拼成後，圖形（2）（4）（5）（6）壹定是黑、白各2格，而圖形（3）必須有3格是同壹種顏色，另壹種顏色1格。因為前四種圖形，黑、白已各占2×4=8（格），而黑格總***只有10格，所以圖形（3）只能是3白1黑。由此知道圖（1）壹定在中間壹列的黑格，而上面的黑格不可能，所以圖（1）在中間壹列下面的黑格中。
那麽其它圖形如何拼呢？為了說明方便，給每壹格編壹個數碼（見左下圖）。
因為圖（3）是3白1黑，所以為使角上不空出壹格，它只能放在（1，3，4，5）或（7，12，13，17）或（11，15，16，21）這三個位置上。
若放在（1，3，4，5）位置上，則圖（6）只能放在（7，12，13，18）或（15，16，19，20）或（2，7，8，13）這三個位置，但是前兩個位置是明顯不行的，否則角上會空出壹格。若放在（2，7，8，13）上，則圖（2）只能放在（12，17，18，19）位置上，此時不能同時放下圖（4）和圖（5）。
若把圖（3）放在（7，12，13，17）位置上，則方格1這壹格只能由圖（2）或圖（6）來占據。如果圖（2）放在（1，2，3，4），那麽圖（6）無論放在何處都要出現孤立空格；如果把圖（6）放在（1，4，5，10），那麽2，3這兩格放哪壹圖形都不合適。
因此，圖形（3）只能放在（11，15，16，21）。其余圖的拼法如右上圖。
練習12
1.中國象棋盤的任意位置有壹只馬，它跳了若幹步正好回到原來的位置。問：馬所跳的步數是奇數還是偶數？
2.右圖是某展覽大廳的平面圖，每相鄰兩展覽室之間都有門相通。今有人想從進口進去，從出口出來，每間展覽廳都要走到，既不能重復也不能遺漏，應如何走法？
3.能否用下圖中各種形狀的紙片（不能剪開）拼成壹個邊長為99的正方形（圖中每個小方格的邊長為1）？請說明理由。
4.用15個1×4的長方形和1個2×2的正方形，能否覆蓋8×8的棋盤？
5.平面上不***線的五點，每兩點連壹條線段，並將每條線段染成紅色或藍色。如果在這個圖形中沒有出現三邊同色的三角形，那麽這個圖形壹定可以找到壹紅壹藍兩個“圈”（即封閉回路），每個圈恰好由五條線段組成。
6.將正方形ABCD分割成n2個相等的小正方格，把相對的頂點A，C染成紅色，B，D染成藍色，其他交點任意染成紅、藍兩種顏色之壹。試說明：恰有三個頂點同色的小方格的數目是偶數。
7.已知△ABC內有n個點，連同A，B，C三點壹***（n＋3）個點。以這些點為頂點將△ABC分成若幹個互不重疊的小三角形。將A，B，C三點分別染成紅色、藍色和黃色。而三角形內的n個點，每個點任意染成紅色、藍色和黃色三色之壹。問：三個頂點顏色都不同的三角形的個數是奇數還是偶數？
8.從10個英文字母A，B，C，D，E，F，G，X，Y，Z中任意選5個字母（字母允許重復）組成壹個“詞”，將所有可能的“詞”按“字典順序”（即英漢辭典中英語詞匯排列的順序）排列，得到壹個“詞表”：
AAAAA，AAAAB，…，AAAAZ，
AAABA，AAABB，…，ZZZZY，ZZZZZ。
設位於“詞”CYZGB與“詞”XEFDA之間（這兩個詞除外）的“詞”的個數是k，試寫出“詞表”中的第k個“詞”。
練習12
1.偶數。
解：把棋盤上各點按黑白色間隔進行染色（圖略）。馬如從黑點出發，壹步只能跳到白點，下壹步再從白點跳到黑點，因此，從原始位置起相繼經過：白、黑、白、黑……要想回到黑點，必須黑、白成對，即經過偶數步，回到原來的位置。
2.不能。
解：用白、黑相間的方法對方格進行染色（如圖）。若滿足題設要求的走法存在，必定從白色的展室走到黑色的展室，再從黑色的展室走到白色的展室，如此循環往復。現***有36間展室，從白色展室開始，最後應該是黑色展室。但右圖中出口處的展室是白色的，矛盾。由此可以判定符合要求的走法不存在。
3.不能。
解：我們將 99×99的正方形中每個單位正方形方格染上黑色或白色，使每兩個相鄰的方格顏色不同，由於 99×99為奇數，兩種顏色的方格數相差為1。而每壹種紙片中，兩種顏色的方格數相差數為0或3，如果它們能拼成壹個大正方形，那麽其中兩種顏色之差必為3的倍數。矛盾！
4.不能。
解：如圖，給8×8的方格棋盤塗上4種不同的顏色（用數字1，2，3，4表示）。顯然標有1，2，3，4的小方格各有16個。每個1×4的長方形恰好蓋住標有1，2，3，4的小方格各壹個，但壹個2×2的正方形只能蓋住有三種數字的方格，故無法將每個方格蓋住，即不可能有題目要求的覆蓋。
5.證：設五點為A，B，C，D，E。考慮從A點引出的四條線段：如果其中有三條是同色的，如AB，AC，AD同為紅色，那麽△BCD的三邊中，若有壹條是紅色，則有壹個三邊同為紅色的三角形；若三邊都不是紅色，則存在壹個三邊同為藍色的三角形。這與已知條件是矛盾的。
所以，從A點出發的四條線段，有兩條是紅色的，也有兩條是藍色的。當然，從其余四點引出的四條線段也恰有兩條紅色、兩條藍色，整個圖中恰有五條紅色線段和五條藍色線段。
下面只看紅色線段，設從A點出發的兩條是AB，AE。再考慮從B點出發的另壹條紅色線段，它不應是BE，否則就有壹個三邊同為紅色的三角形。不妨設其為BD。再考慮從D點出發的另壹條紅色線段，它不應是DE，否則從C引出的兩條紅色線段就要與另壹條紅色線段圍成壹個紅色三角形，故它是DC。最後壹條紅色線段顯然是CE。這樣就得到了壹個紅色的“圈”：
A→B→D→C→E→A。
同理，五條藍線也構成壹個“圈”。
6.證：將紅點賦值為0，藍點賦值為1。再將小方格四頂點上的數的和稱為這個小方格的值。若恰有三頂點同色，則該小方格的值為奇數，否則為偶數。在計算所有n2個小方格之值的和時，除A，B，C，D只計算壹次外，其余各點都被計算了兩次或四次。因為A，B，C，D四個點上的數之和是偶數，所以n2個小方格之值的和是偶數，從而這n2個值中有偶數個奇數。
7.奇數。
解：先對所有的小三角形的邊賦值：邊的兩端點同色，該線段賦值為0，邊的兩端點不同色，該線段賦值為1。
然後計算每個小三角形的三邊賦值之和，有如下三種情況：
（1）三個頂點都不同色的三角形，賦值和為3；
（2）三個頂點中恰有兩個頂點同色的三角形，賦值和為2；
（3）三個頂點同色的三角形，賦值和為0。
設所有三角形的邊賦值總和為S，又設（1）（2）（3）三類小三角形的個數分別為a，b，c，於是有
S=3a+2b+0c=3a+2b。（*）
註意到在所有三角形的邊賦值總和中，除了AB，BC，CA三條邊外，都被計算了兩次，故它們的賦值和是這些邊賦值和的2倍，再加上△ABC的三邊賦值和3，從而S是壹個奇數，由（*）式知a是壹個奇數，即三個頂點顏色都不同的三角形的個數是壹個奇數。
8.EFFGY。
解：將A，B，C，D，E，F，G，X，Y，Z分別賦值為0，1，2，3，4，5，6，7，8，9，則
CYZGB=28961，_XEFDA=74530。
在28961與74530之間***有74530-28961-1=45568（個）數，詞表中第45568個詞是EFFGY。