-染色問題與染色方法

　　1. 小方格染色問題

　　最簡單的染色問題是從一種民間游戲中發(fā)展起來的方格盤上的染色問題.解決這類問題的方法后來又發(fā)展成為解決方格盤鋪蓋問題的重要技巧.

　　例1 如圖29-1(a),3行7列小方格每一個染上紅色或藍(lán)色.試證:存在一個矩形,它的四個角上的小方格顏色相同.

　　證明 由抽屜原則,第1行的7個小方格至少有4個不同色,不妨設(shè)為紅色(帶陰影)并在1、2、3、4列(如圖29-1(b)).

　　在第1、2、3、4列(以下不必再考慮第5，6，7列)中，如第2行或第3行出現(xiàn)兩個紅色小方格，則這個問題已經(jīng)得證;如第2行和第3行每行最多只有一個紅色小方格(如圖29-1(c))，那么在這兩行中必出現(xiàn)四角同為藍(lán)色的矩形，問題也得到證明.

　　說明：(1)在上面證明過程中除了運用抽屜原則外，還要用到一種思考問題的有效方法，就是逐步縮小所要討論的對象的范圍，把復(fù)雜問題逐步化為簡單問題進(jìn)行處理的方法.

　　(2)此例的行和列都不能再減少了.顯然只有兩行的方格盤染兩色后是不一定存在頂點同色的矩形的.下面我們舉出一個3行6列染兩色不存在頂點同色矩形的例子如圖29-2.這說明3行7列是染兩色存在頂點同色的矩形的最小方格盤了.至今,染k色而存在頂點同色的矩形的最小方格盤是什么還不得而知.

　　例2 (第2屆全國部分省市初中數(shù)學(xué)通訊賽題)證明:用15塊大小是4×1的矩形瓷磚和1塊大小是2×2的矩形瓷磚，不能恰好鋪蓋8×8矩形的地面.

　　分析 將8×8矩形地面的一半染上一種顏色，另一半染上另一種顏色，再用4×1和2×2的矩形瓷磚去蓋，如果蓋住的兩種顏色的小矩形不是一樣多，則說明在給定條件不完滿鋪蓋不可能.

　　證明 如圖29-3，用間隔為兩格且與副對角線平行的斜格同色的染色方式，以黑白兩種顏色將整個地面的方格染色.顯然，地面上黑、白格各有32個.

　　每塊4×1的矩形磚不論是橫放還是豎蓋，且不論蓋在何處，總是占據(jù)地面上的兩個白格、兩個黑格，故15塊4×1的矩形磚鋪蓋后還剩兩個黑格和兩個白格.但由于與副對角線平行的斜格總是同色，而與主對角線平行的相鄰格總是異色，所以，不論怎樣放置，一塊2×2的矩形磚，總是蓋住三黑一白或一黑三白.這說明剩下的一塊2×2矩形磚無論如何蓋不住剩下的二黑二白的地面.從而問題得證.

　　例3 (1986年北京初二數(shù)學(xué)競賽題)如圖29-4(1)是4個1×1的正方形組成的“L”形，用若干個這種“L”形硬紙片無重迭拼成一個m×n(長為m個單位，寬為n個單位)的矩形如圖29-4(2).試證明mn必是8的倍數(shù).

　　證明∵m×n矩形由“L”形拼成，∴m×n是4的倍數(shù)，∴m、n中必有一個是偶數(shù)，不妨設(shè)為m.把m×n矩形中的m列按一列黑、一列白間隔染色(如圖29-4(2))，則不論“L”形在這矩形中的放置位置如何(“L”形的放置，共有8種可能)，“L”形或占有3白一黑四個單位正方形(第一種)，或占有3黑一白四個單位正方形(第二種).

　　設(shè)第一種“L”形共有p個，第二種“L”形共q個，則m×n矩形中的白格單位正方形數(shù)為3p+q，而它的黑格單位正方形數(shù)為p+3q.

　　∵m為偶數(shù)，∴m×n矩形中黑、白條數(shù)相同，黑、白單位正方形總數(shù)也必相等.故有3p+q=p+3q，從而p=q.所以“L”形的總數(shù)為2p個，即“L”形總數(shù)為偶數(shù)，所以m×n一定是8的倍數(shù).