第25講-染色問題與染色方法

1、第25講 染色問題與染色方法數(shù)學(xué)家像畫家和詩人一樣，是模式制造家。 G.H.哈代知識(shí)方法掃描染色是分類的直觀表現(xiàn)，在數(shù)學(xué)競賽中有大批以染色面目出現(xiàn)的問題，這類問題的特點(diǎn)是知識(shí)點(diǎn)少，邏輯性強(qiáng)，技巧性強(qiáng)，其內(nèi)部蘊(yùn)藏著深刻的數(shù)學(xué)思想.同時(shí)，染色作為一種解題手段也在數(shù)學(xué)競賽中廣泛使用.1. 染色問題解答染色問題，并不需要具備更多的數(shù)學(xué)知識(shí)，只需要具有縝密的思考能力和較強(qiáng)的分析能力.縱觀各種染色試題，它與我們經(jīng)常使用的數(shù)學(xué)方法緊密聯(lián)系.大體上有如下幾種方法：奇偶分析、歸納法、反證法、抽屜原理、構(gòu)造法、組合計(jì)數(shù)等.2. 染色方法將問題中的對象適當(dāng)進(jìn)行染色，有利于我們觀察、分析對象之間的關(guān)系，像國際象棋的棋

2、盤那樣，我們可以把被研究的對象染上不同的顏色，許多隱藏的關(guān)系會(huì)變得明了，再通過對染色圖形的處理達(dá)到對原問題的解決，這種解題方法稱為染色法.常見的染色方式有：點(diǎn)染色、線段染色、小方格染色和對區(qū)域染色.經(jīng)典例題解析例1 用任意的方式將平面上的每一點(diǎn)染上黑色或白色(稱為二染色).求證：一定存在長為1的線段，它的兩個(gè)端點(diǎn)同色.分析 在平面上任畫一條長為1的線段，如圖，若A，B兩點(diǎn)同色，則結(jié)論已成立.若A，B兩點(diǎn)不同色，為確定起見不妨設(shè)A為黑色，B為白色，以AB為邊作正三角形ABC，則AB=BC=CA=1.這時(shí)C點(diǎn)要么是黑點(diǎn)，要么是白點(diǎn).若C為黑點(diǎn)，則AC為兩個(gè)端點(diǎn)同色的長為1的線段.若C為白點(diǎn)，則BC

3、為兩個(gè)端點(diǎn)同色的長為1的線段.上述分析過程，其實(shí)已完成了證明過程，不過思路一旦找出，出現(xiàn)邊長為1的正三角形的頂點(diǎn)A，B，C三點(diǎn)的構(gòu)想是個(gè)關(guān)鍵，為此可得出如下簡化的證明.證明 在平面上任作一個(gè)邊長為1的正三角形，設(shè)三個(gè)頂點(diǎn)為A，B，C，由于平面上的每點(diǎn)只著黑、白兩色之一，根據(jù)抽屜原理，A，B，C三點(diǎn)中必有兩點(diǎn)同色，以這兩同色點(diǎn)為端點(diǎn)的線段長度恰為1.評注 由例1可得更一般的結(jié)論：平面上的點(diǎn)二染色后，一定存在長為a(a0)的線段，它的兩個(gè)端點(diǎn)同色.例2 對平面上的點(diǎn)黑白二染色后，一定存在三頂點(diǎn)同色的直角三角形.證明 對平面上的點(diǎn)黑白二染色，根據(jù)例1的結(jié)論，存在邊長為a(a0)的線段AB，它的兩個(gè)端

4、點(diǎn)同色(不妨設(shè)A，B同黑).以AB為邊作正方形ABCD，對角線AC，BD交于點(diǎn)O，如圖，如果D，O，C中有一個(gè)黑點(diǎn)，則該點(diǎn)與A，B構(gòu)成三頂點(diǎn)同黑色的直角三角形.如果D，O，C全白色，則DOC就是三頂點(diǎn)全為白色的直角三角形.因此，二染色平面上一定存在頂點(diǎn)同色的直角三角形.評注 進(jìn)一步由圖證明可得：二染色平面上存在斜邊要么為a，要么為a且三頂點(diǎn)同色的等腰直角三角形.那么，當(dāng)平面點(diǎn)二染色以后，是否一定存在邊長為1且頂點(diǎn)同色的等邊三角形呢？例3將對這個(gè)問題作出回答.例3 用任意的方式，對平面上的每個(gè)點(diǎn)染黑色或白色，求證：一定存在一個(gè)邊長為1或的正三角形，它的三個(gè)頂點(diǎn)同色.證明 若存在邊長為1且頂點(diǎn)同色

5、的正三角形，則問題得證.若不存在邊長為1且頂點(diǎn)同色的正三角形，則一定存在長為1的線段AB，兩端點(diǎn)A，B異色.以AB=1為底作腰長為2的等腰三角形ABC，則C與A或B總有一對是異色的.不妨設(shè)長為2的線段AC兩端點(diǎn)異色(見圖(a).取AC的中點(diǎn)O，則O必與A，C之一同色(見圖(b)，不妨設(shè)O與A同色.由于不存在邊長為1的同色頂點(diǎn)的正三角形，所以以AO為一邊的等邊三角形的另外的頂點(diǎn)D和E必與A異色.此時(shí)，ECD就是一個(gè)邊長為的頂點(diǎn)同色的正三角形.評注 事實(shí)上，當(dāng)將平面分成寬度為的水平帶狀區(qū)域，且每個(gè)區(qū)域含下沿直線，不含上沿直線，使相鄰的帶狀區(qū)域染上不同顏色，對這樣的平面二染色，任意邊長為1的正三角形

6、的三個(gè)頂點(diǎn)均不同色，但存在邊長為的三頂點(diǎn)同色的三角形.由例3可得更一般的結(jié)論：平面上點(diǎn)二染色后，要么存在邊長為a(a0)三頂點(diǎn)同色的正三角形，要么存在邊長為 a三頂點(diǎn)同色的正三角形.例4 連接圓周上9個(gè)不同點(diǎn)的36條線段染成紅色或藍(lán)色，假設(shè)9點(diǎn)中每3點(diǎn)所確定的三角形都至少含有一條紅色邊.證明有4點(diǎn)，其中每兩點(diǎn)的連線都是紅色.證明 設(shè)9個(gè)點(diǎn)依次為v，v，v，首先證明必存在一點(diǎn)，設(shè)為v，從v出發(fā)的紅色線段不是5條.事實(shí)上，若不然，如果都是5條，則共有紅色線段不是整數(shù)，矛盾.若從v出發(fā)的紅色線段至少有6條，設(shè)vv，vv，vv，vv，vv，vv均為紅色，則由第26講例8評注可知，連結(jié)v，v，v，v，v

7、，v的線段中必有同色三角形.由題意知它只能為紅色三角形，設(shè)為vvv，則v，v，v，v四點(diǎn)中兩兩皆連紅線.若從v出發(fā)的紅色線段至多4條，則v出發(fā)的藍(lán)色線段至少有4條，設(shè)為vv，vv，vv，vv，則v，v，v，v4點(diǎn)必然兩兩連紅線.否則，例如若vv是藍(lán)色的，則vvv是藍(lán)色三角形，與題設(shè)至少有一邊為紅色矛盾.以上各例中，染色都是作為問題條件給出的，有時(shí)，染色方法也作為一種分類手段，因此，用形象直觀地染色進(jìn)行分類，也就成了一種很有特色的解題方法.例5 某橋牌俱樂部約定，四個(gè)人在一起打牌，同一方的兩個(gè)人必須都曾合作過，或都不曾合作過.試證：只要有五個(gè)人，就一定能湊齊四個(gè)人，按照約定在一起打牌.分析 本題

8、證明采用構(gòu)造一個(gè)涂色模型，使它與原問題間有一一對應(yīng)的關(guān)系.如果模型中的問題證明了，那么原問題也相應(yīng)地證明了.證明 五個(gè)人對應(yīng)為空間五個(gè)點(diǎn)，如兩個(gè)人合作過，那么對應(yīng)兩點(diǎn)連結(jié)紅色線段，如兩人不曾合作過，那么對應(yīng)兩點(diǎn)連結(jié)藍(lán)色線段.因此原問題等價(jià)于證明涂色模型：空間五個(gè)點(diǎn)(無三點(diǎn)在一條直線上)，兩兩連線，涂上紅色或藍(lán)色之一.證明必存在兩條無公共端點(diǎn)的同色線段.設(shè)五個(gè)點(diǎn)為A，A，A，A，A，不失一般性，不妨設(shè)AA為紅色.觀察AAA三條邊的顏色.(1)如果AAA中有一條邊為紅色，設(shè)為AA，那么AA與AA是滿足條件的兩條線段；(2)如果AAA的三條邊均為藍(lán)色，此時(shí)如AA，AA，AA與AA，AA，AA中如果有

9、一條藍(lán)色線段，那么問題就獲證.如以AA是藍(lán)色線段為例，那么AA與AA是滿足條件的兩條線段.反之，如果此時(shí)六條線段均為紅色，如取AA與AA就是滿足條件的兩條線段.由于無公共端點(diǎn)的同色線段存在，證得原命題成立.例6 把平面劃分成形為全等正六邊形的房間，并按如下辦法開門：若三面墻匯聚于一點(diǎn)，那么在其中兩面墻上各開一個(gè)門，而第三面墻不開門.證明：不論沿多么曲折的路線走回原來的房間，所穿過的門的個(gè)數(shù)一定是偶數(shù).分析與解 為方便起見，我們把有公共門的兩個(gè)房間叫做相鄰的.用兩種不同的顏色涂平面上的這些房間，使相鄰的房間的顏色不同(如圖).注意，從某種顏色的房間走到同種顏色的房間，必須經(jīng)過另一種顏色的房間.顯

10、然，從任一房間走到同種顏色的房間，必定經(jīng)過偶數(shù)個(gè)門.這樣，利用圖形和不同的顏色就可以解出這道題.例7 有一個(gè)20032003的棋盤和任意多個(gè)l2及13的矩形紙片，規(guī)定l2的紙片只能沿著棋盤的格線水平地放置，而13的紙片只能沿著棋盤的格線鉛直地放置. 請問是否可依上述規(guī)定取用一些紙片不重疊地蓋滿整個(gè)棋盤？分析與解 先將棋盤的每一行黑白交錯(cuò)涂色，即第一行，第二行，第三行，依次為黑色，白色，黑色，.經(jīng)過這樣涂色后，開始時(shí)棋盤的黑白方格數(shù)之差為2003個(gè).沿著棋盤的格線水平地放置12的紙片，每放上一個(gè)l2的紙片，就能蓋住黑白方格各一個(gè)，所以這個(gè)操作并不會(huì)改變黑白方格數(shù)之差；而每一個(gè)13的矩形紙片沿著棋

11、盤的格線鉛直地放置，所覆蓋的三個(gè)方格都是同一顏色，所以每放置一片l3的矩形紙片，棋盤的黑白方格數(shù)之差就增加3個(gè)或減少3個(gè).因?yàn)?003不是3的倍數(shù)，所以，依題述規(guī)定取用一些12及l(fā)3的矩形紙片是不可能不重疊地蓋滿整個(gè)棋盤的.例8 證明：如圖，用15塊4×1的矩形瓷磚與1塊2×2的方形瓷磚，不能覆蓋8×8的正方形地面(瓷磚不許斷開！).分析 本例題有多種證法.一個(gè)共同點(diǎn)是：“不能覆蓋”的證明，通常借助于反證法.證法1 將8×8的正方形地面的小方格，用黑、白色涂之，染色法如圖.于是，每一塊4×1瓷磚，不論怎樣輔設(shè)，都恰好蓋住兩個(gè)白格兩個(gè)黑格.15塊

12、4×1瓷磚共蓋住30個(gè)白格和30個(gè)黑格.一塊2×2瓷磚，無論怎么放，總是蓋住“三白一黑”或“三黑一白”，即只能蓋住奇數(shù)個(gè)白格和奇數(shù)個(gè)黑格.而盤中的黑白格總數(shù)相等(全為32個(gè)).所以用15塊4×1磚與1塊2×2磚不能完全覆蓋8×8地面.證法2 將8×8的正方形地面的小方格.用代號(hào)為1，2，3，4的四種顏色涂之，染色法如(a).這時(shí)，4×1磚每次總能蓋住1，2，3，4四色；而2×2磚不論放何處，總是不能同時(shí)蓋住1，2，3，4四色.故是不可能的.證法3 同樣用四色涂之，涂法如(b).用反證法，設(shè)4×1磚橫著蓋住

13、i色的有x塊，豎著蓋住的有y塊.2×2磚蓋住陰影格處(不妨假定，余仿此).假定能夠蓋住.那么有：相減得4(xx)=2.因?yàn)閤與x均為整數(shù)，這是不可能的.同步訓(xùn)練1.有10個(gè)表面涂滿紅漆的正方體，其棱長分別為2，4，6，20.若把這些正方體全部鋸成棱長為1的小正方體，求有多少個(gè)至少一面有漆的小正方體.2.將直線上的每一個(gè)點(diǎn)都染上紅、黃兩色中的一種，證明：必存在同顏色的三個(gè)點(diǎn)，使得其中一點(diǎn)是另兩點(diǎn)為端點(diǎn)的線段的中點(diǎn).3.在二染色的平面上一定存在一個(gè)矩形，它的四個(gè)頂點(diǎn)同色.4.將正方體的每一個(gè)面分成四個(gè)相等的正方形，從三種不同顏色中任選一種給一個(gè)正方形染色，且使任何兩個(gè)有公共邊的正方形染不

14、同的顏色.證明：每種顏色恰好染8個(gè)正方形.并舉出一種染色方案.5.某班有50個(gè)學(xué)生，男女各占一半，他們圍成一圈，席地而坐開營火晚會(huì)，求證：必能找到一位兩旁都是女生的學(xué)生.6.在2n×2n的棋盤上，把相對角的兩格剪去，則不能用若干塊1×2的小棋盤(又稱為多米諾骨牌)無重迭地覆蓋這個(gè)缺角的大棋盤.7.有一種計(jì)算機(jī)軟件只能復(fù)制一個(gè)邊長為1的正方形的四個(gè)邊，然后貼上。請問要構(gòu)造出一幅的方格表，至少總共要貼上幾個(gè)正方形？8.求證：8×8國際象棋盤不可能被剪成7個(gè)2×2正方形小棋盤與9個(gè)1×4小長條.9. 若由“L”形的4個(gè)小方格，無重迭地拼成一個(gè)m×n的矩形.試證：m×n必為8的倍數(shù). 10. 設(shè)A，A，A是平面上的六點(diǎn)，其中任三點(diǎn)不共線.如果這些點(diǎn)之間任意連接了13條線段，證明：必存在四點(diǎn)，它們每兩點(diǎn)之間都有線段連接.11. 將一個(gè)棱長分別為36厘米、54厘米和72厘米的長方體切割成一些大小相同、棱長是整數(shù)厘米的正方體，然后給這些正方體的表面涂色。有一高為1厘米、半徑為6厘米圓柱體桶，裝有漆，已知每立方厘米的這種漆可以涂色72平