染色問(wèn)題與染色方法

1、染色問(wèn)題與染色方法1  小方格染色問(wèn)題最簡(jiǎn)單的染色問(wèn)題是從一種民間游戲中發(fā)展起來(lái)的方格盤(pán)上的染色問(wèn)題.解決這類(lèi)問(wèn)題的方法后來(lái)又發(fā)展成為解決方格盤(pán)鋪蓋問(wèn)題的重要技巧.例1 如圖29-1(a),3行7列小方格每一個(gè)染上紅色或藍(lán)色.試證:存在一個(gè)矩形,它的四個(gè)角上的小方格顏色相同.證明  由抽屜原則,第1行的7個(gè)小方格至少有4個(gè)不同色,不妨設(shè)為紅色(帶陰影)并在1、2、3、4列（如圖29-1（b）.在第1、2、3、4列（以下不必再考慮第5，6，7列）中，如第2行或第3行出現(xiàn)兩個(gè)紅色小方格，則這個(gè)問(wèn)題已經(jīng)得證；如第2行和第3行每行最多只有一個(gè)紅色小方格（如圖29-1（c），那么在這

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

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

4、由于與副對(duì)角線平行的斜格總是同色，而與主對(duì)角線平行的相鄰格總是異色，所以，不論怎樣放置，一塊2×2的矩形磚，總是蓋住三黑一白或一黑三白.這說(shuō)明剩下的一塊2×2矩形磚無(wú)論如何蓋不住剩下的二黑二白的地面.從而問(wèn)題得證.   例3 （1986年北京初二數(shù)學(xué)競(jìng)賽題）如圖29-4（1）是4個(gè)1×1的正方形組成的“L”形，用若干個(gè)這種“L”形硬紙片無(wú)重迭拼成一個(gè)m×n（長(zhǎng)為m個(gè)單位，寬為n個(gè)單位）的矩形如圖29-4（2）.試證明mn必是8的倍數(shù).證明m×n矩形由“L”形拼成，m×n是4的倍數(shù)，m、n中必有一個(gè)是偶數(shù)，

5、不妨設(shè)為m.把m×n矩形中的m列按一列黑、一列白間隔染色（如圖29-4（2），則不論“L”形在這矩形中的放置位置如何（“L”形的放置，共有8種可能），“L”形或占有3白一黑四個(gè)單位正方形（第一種），或占有3黑一白四個(gè)單位正方形（第二種）.設(shè)第一種“L”形共有p個(gè)，第二種“L”形共q個(gè)，則m×n矩形中的白格單位正方形數(shù)為3p+q，而它的黑格單位正方形數(shù)為p+3q.m為偶數(shù)，m×n矩形中黑、白條數(shù)相同，黑、白單位正方形總數(shù)也必相等.故有3p+q=p+3q，從而p=q.所以“L”形的總數(shù)為2p個(gè)，即“L”形總數(shù)為偶數(shù)，所以m×n一定是8的倍數(shù). &#

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

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

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

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

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

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

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

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

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