染色問題與染色方法

1、染色問題與染色方法1  小方格染色問題最簡單的染色問題是從一種民間游戲中發(fā)展起來的方格盤上的染色問題.解決這類問題的方法后來又發(fā)展成為解決方格盤鋪蓋問題的重要技巧.例1 如圖29-1(a),3行7列小方格每一個染上紅色或藍色.試證:存在一個矩形,它的四個角上的小方格顏色相同.證明  由抽屜原則,第1行的7個小方格至少有4個不同色,不妨設為紅色(帶陰影)并在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），那么在這

2、兩行中必出現(xiàn)四角同為藍色的矩形，問題也得到證明.說明：（1）在上面證明過程中除了運用抽屜原則外，還要用到一種思考問題的有效方法，就是逐步縮小所要討論的對象的范圍，把復雜問題逐步化為簡單問題進行處理的方法.（2）此例的行和列都不能再減少了.顯然只有兩行的方格盤染兩色后是不一定存在頂點同色的矩形的.下面我們舉出一個3行6列染兩色不存在頂點同色矩形的例子如圖29-2.這說明3行7列是染兩色存在頂點同色的矩形的最小方格盤了.至今,染k色而存在頂點同色的矩形的最小方格盤是什么還不得而知.例2  (第2屆全國部分省市初中數(shù)學通訊賽題)證明:用15塊大小是4×1的矩形瓷磚和1塊

3、大小是2×2的矩形瓷磚，不能恰好鋪蓋8×8矩形的地面.分析  將8×8矩形地面的一半染上一種顏色，另一半染上另一種顏色，再用4×1和2×2的矩形瓷磚去蓋，如果蓋住的兩種顏色的小矩形不是一樣多，則說明在給定條件不完滿鋪蓋不可能.證明  如圖29-3，用間隔為兩格且與副對角線平行的斜格同色的染色方式，以黑白兩種顏色將整個地面的方格染色.顯然，地面上黑、白格各有32個.每塊4×1的矩形磚不論是橫放還是豎蓋，且不論蓋在何處，總是占據(jù)地面上的兩個白格、兩個黑格，故15塊4×1的矩形磚鋪蓋后還剩兩個黑格和兩個白格.但

4、由于與副對角線平行的斜格總是同色，而與主對角線平行的相鄰格總是異色，所以，不論怎樣放置，一塊2×2的矩形磚，總是蓋住三黑一白或一黑三白.這說明剩下的一塊2×2矩形磚無論如何蓋不住剩下的二黑二白的地面.從而問題得證.   例3 （1986年北京初二數(shù)學競賽題）如圖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ù)，

5、不妨設為m.把m×n矩形中的m列按一列黑、一列白間隔染色（如圖29-4（2），則不論“L”形在這矩形中的放置位置如何（“L”形的放置，共有8種可能），“L”形或占有3白一黑四個單位正方形（第一種），或占有3黑一白四個單位正方形（第二種）.設第一種“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ù). &#

6、160;   2 線段染色和點染色下面介紹兩類重要的染色問題.(1)    線段染色.較常見的一類染色問題是發(fā)樣子組合數(shù)學中圖論知識的所謂“邊染色”（或稱“線段染色”），主要借助抽屜原則求解.例4         （1947年匈牙利數(shù)學奧林匹克試題）世界上任何六個人中，一定有3個人或者互相認識或者互相都不認識.我們不直接證明這個命題，而來看與之等價的下述命題例5 （1953年美國普特南數(shù)學競賽題）空間六點，任三點不共線，任四點不共面，成對地連接它

7、們得十五條線段，用紅色或藍色染這些線段（一條線段只染一種顏色）.求證:無論怎樣染,總存在同色三角形.證明  設A、B、C、D、E、F是所給六點.考慮以A為端點的線段AB、AC、AD、AE、AF，由抽屜原則這五條線段中至少有三條顏色相同，不妨設就是AB、AC、AD，且它們都染成紅色.再來看BCD的三邊，如其中有一條邊例如BC是紅色的，則同色三角形已出現(xiàn)（紅色ABC）；如BCD三邊都不是紅色的，則它就是藍色的三角形，同色三角形也現(xiàn)了.總之,不論在哪種情況下,都存在同色三角形.如果將例4中的六個人看成例5中六點,兩人認識的連紅線,不認識的連藍線,則例4就變成了例5.例5的證明實際上用染色方

8、法給出了例4的證明.例6  (第6屆國際數(shù)學奧林匹克試題)有17位科學家,其中每一個人和其他所有人的人通信,他們的通信中只討論三個題目.求證:至少有三個科學家相互之間討論同一個題目.證明  用平面上無三點共線的17個點A1,A2,，A17分別表示17位科學家.設他們討論的題目為x,y,z,兩位科學家討論x連紅線,討論y連藍線,討論z連黃線.于是只須證明以這17個點為頂點的三角形中有一同色三角形.考慮以A1為端點的線段A1A2,A1A3,，A1A17，由抽屜原則這16條線段中至少有6條同色，不妨設A1A2，A1A3，A1A7為紅色.現(xiàn)考查連結(jié)六點A2，A3，A7的1

9、5條線段，如其中至少有一條紅色線段，則同色（紅色）三角形已出現(xiàn)；如沒有紅色線段，則這15條線段只有藍色和黃色，由例5知一定存在以這15條線段中某三條為邊的同色三角形（藍色或黃色）.問題得證.上述三例同屬圖論中的接姆賽問題.在圖論中,將n點中每兩點都用線段相連所得的圖形叫做n點完全圖,記作kn.這些點叫做“頂點”，這些線段叫做“邊”.現(xiàn)在我們分別用圖論的語言來敘述例5、例6.定理1  若在k6中，任染紅、藍兩色，則必有一只同色三角形.定理2  在k17中,任染紅、藍、黃三角，則必有一只同色三角形.（2）點染色.先看離散的有限個點的情況.例7 （首屆全國中學生數(shù)學冬令

10、營試題）能否把1，1，2，2，3，3，1986，1986這些數(shù)排成一行，使得兩個1之間夾著一個數(shù)，兩個2之間夾著兩個數(shù)，兩個1986、之間夾著一千九百八十六個數(shù)？請證明你的結(jié)論.證明  將1986×2個位置按奇數(shù)位著白色，偶數(shù)位著黑色染色，于是黑白點各有1986個.現(xiàn)令一個偶數(shù)占據(jù)一個黑點和一個白色，同一個奇數(shù)要么都占黑點，要么都占白點.于是993個偶數(shù)，占據(jù)白點A1=993個，黑色B1=993個.993個奇數(shù)，占據(jù)白點A2=2a個，黑點B2=2b個，其中a+b=993.因此，共占白色A=A1+A2=993+2a個. 黑點B=B1+B2=993+2b個，由于a+b=993（

11、非偶數(shù)?。゛b，從而得AB.這與黑、白點各有1986個矛盾.故這種排法不可能.“點”可以是有限個，也可以是無限個，這時染色問題總是與相應的幾何問題聯(lián)系在一起的.例8 對平面上一個點，任意染上紅、藍、黑三種顏色中的一種.證明:平面內(nèi)存在端點同色的單位線段.證明  作出一個如圖29-7的幾何圖形是可能的,其中ABD、CBD、AEF、GEF都是邊長為1的等邊三角形，CG=1.不妨設A點是紅色，如果B、E、D、F中有紅色，問題顯然得證.當B、E、D、F都為藍點或黃點時，又如果B和D或E和F同色，問題也得證.現(xiàn)設B和D異色E和F異色,在這種情況下,如果C或G為黃色或藍點,則CB、CD

12、、GE、GF中有兩條是端點同色的單位線段，問題也得證.不然的話,C、G均為紅點，這時CG是端點同色的單位線段.證畢.還有一類較難的對區(qū)域染色的問題，就不作介紹了.練習1  6×6的方格盤，能否用一塊大小為3格，形如的彎角板與11塊大小為3×1的矩形板，不重迭不遺漏地來鋪滿整個盤面.2  （第49屆蘇聯(lián)基輔數(shù)學競賽題）在兩張1982×1983的方格紙涂上紅、黑兩種顏色，使得每一行及每一列都有偶數(shù)個方格是黑色的.如果將這兩張紙重迭時，有一個黑格與一個紅格重合，證明至少還有三個方格與不同顏色的方格重合.3  有九名數(shù)學家，每人至多會講三種語

13、言，每三名中至少有2名能通話，那么其中必有3名能用同一種語言通話.4  如果把上題中的條件9名改為8名數(shù)學家，那么，這個結(jié)論還成立嗎？為什么？5  設n=6（r-2）+3（r3），求證：如果有n名科學家，每人至多會講3種語言，每3名中至少有2名能通話，那么其中必有     r名能用同一種語言通話.6  （1966年波蘭數(shù)學競賽題）大廳中會聚了100個客人，他們中每人至少認識67人，證明在這些客人中一定可以找到4人，他們之中任何兩人都彼此相識.7  （首屆全國數(shù)學冬令營試題）用任意方式給平面上的每一個點染上黑色或白色

14、.求證：一定存在一個邊長為1或的正三角形，它三個頂點是同色的.練習答案將、行染紅色、行染黃色、行染藍色，然后就彎角板蓋住板面的不同情況分類討論設第一張紙上的黑格與第二張紙上的紅格重合如果在第一張紙上所在的列中，其余的黑格（奇數(shù)個）均與第二張紙的黑格重合，那么由第二張紙上這一列的黑格個數(shù)為偶數(shù)，知必有一黑格與第一張紙上的紅格重合，即在這一列，第一張紙上有一方格與第二張紙上不同顏色的方格重合同理在、所在行上各有一個方格、，第二張紙上與它們重合的方格、的顏色分別與、不同把名數(shù)學家用點，表示兩人能通話，就用線連結(jié)，并涂某種顏色，以表示不同語種。兩人不通話，就不連線（）果任兩點都有連線并涂有顏色，那么必有一點如，以其為一端點的條線段中至少有兩條同色，比如、可見，之間可用同一語言通話如情況不發(fā)生，則至少有兩點不連線，比如、由題設任三點必有一條連線知，其余七點必與或有連線這時七條線中，必有四條是從某一點如引出的而這四條線中又必有二條同色，則問題得證結(jié)論不成立，如圖所示（圖中每條線旁都有一個數(shù)字，以表示不同語種）類似于第題證明用點、表示客人，紅、藍的連線分別表示兩人相識或不相識，因為由一個頂點引出的藍色的線段最多有條，所以其