資源描述：
《染色問題與染色方法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、染色問題與染色方法1．?小方格染色問題最簡單的染色問題是從一種民間游戲中發(fā)展起來的方格盤上的染色問題.解決這類問題的方法后來又發(fā)展成為解決方格盤鋪蓋問題的重要技巧.例1如圖29-1(a),3行7列小方格每一個染上紅色或藍色.試證:存在一個矩形,它的四個角上的小方格顏色相同.證明?由抽屜原則,第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行每行最多只有一個
2、紅色小方格（如圖29-1（c）），那么在這兩行中必出現(xiàn)四角同為藍色的矩形，問題也得到證明.說明：（1）在上面證明過程中除了運用抽屜原則外，還要用到一種思考問題的有效方法，就是逐步縮小所要討論的對象的范圍，把復(fù)雜問題逐步化為簡單問題進行處理的方法.（2）此例的行和列都不能再減少了.顯然只有兩行的方格盤染兩色后是不一定存在頂點同色的矩形的.下面我們舉出一個3行6列染兩色不存在頂點同色矩形的例子如圖29-2.這說明3行7列是染兩色存在頂點同色的矩形的最小方格盤了.至今,染k色而存在頂點同色的矩形的最小方格盤是什么還不得而知.例2?????
3、???(第2屆全國部分省市初中數(shù)學(xué)通訊賽題)證明:用15塊大小是4×1的矩形瓷磚和1塊大小是2×2的矩形瓷磚，不能恰好鋪蓋8×8矩形的地面.分析?將8×8矩形地面的一半染上一種顏色，另一半染上另一種顏色，再用4×1和2×2的矩形瓷磚去蓋，如果蓋住的兩種顏色的小矩形不是一樣多，則說明在給定條件不完滿鋪蓋不可能.證明?如圖29-3，用間隔為兩格且與副對角線平行的斜格同色的染色方式，以黑白兩種顏色將整個地面的方格染色.顯然，地面上黑、白格各有32個.每塊4×1的矩形磚不論是橫放還是豎蓋，且不論蓋在何處，總是占據(jù)地面上的兩個白格、兩個黑格，
4、故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”形拼成，∴
5、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ù)為
6、2p個，即“L”形總數(shù)為偶數(shù)，所以m×n一定是8的倍數(shù).????2．?線段染色和點染色下面介紹兩類重要的染色問題.(1)???線段染色.較常見的一類染色問題是發(fā)樣子組合數(shù)學(xué)中圖論知識的所謂“邊染色”（或稱“線段染色”），主要借助抽屜原則求解.例4????????（1947年匈牙利數(shù)學(xué)奧林匹克試題）世界上任何六個人中，一定有3個人或者互相認(rèn)識或者互相都不認(rèn)識.我們不直接證明這個命題，而來看與之等價的下述命題例5????????（1953年美國普特南數(shù)學(xué)競賽題）空間六點，任三點不共線，任四點不共面，成對地連接它們得十五條線段，用紅色或藍
7、色染這些線段（一條線段只染一種顏色）.求證:無論怎樣染,總存在同色三角形.證明?設(shè)A、B、C、D、E、F是所給六點.考慮以A為端點的線段AB、AC、AD、AE、AF，由抽屜原則這五條線段中至少有三條顏色相同，不妨設(shè)就是AB、AC、AD，且它們都染成紅色.再來看△BCD的三邊，如其中有一條邊例如BC是紅色的，則同色三角形已出現(xiàn)（紅色△ABC）；如△BCD三邊都不是紅色的，則它就是藍色的三角形，同色三角形也現(xiàn)了.總之,不論在哪種情況下,都存在同色三角形.如果將例4中的六個人看成例5中六點,兩人認(rèn)識的連紅線,不認(rèn)識的連藍線,則例4就變成了
8、例5.例5的證明實際上用染色方法給出了例4的證明.例6????????(第6屆國際數(shù)學(xué)奧林匹克試題)有17位科學(xué)家,其中每一個人和其他所有人的人通信,他們的通信中只討論三個題目.求證:至少有三個科學(xué)家相互之間討論同一個題目.證明?用平
