數(shù)學(xué)奧林匹克競(jìng)賽講座 14染色問(wèn)題及染色方法

1、競(jìng)賽講座競(jìng)賽講座14染色問(wèn)題與染色方法染色問(wèn)題與染色方法1小方格染色問(wèn)題最簡(jiǎn)單的染色問(wèn)題是從一種民間游戲中發(fā)展起來(lái)的方格盤上的染色問(wèn)題.解決這類問(wèn)題的方法后來(lái)又發(fā)展成為解決方格盤鋪蓋問(wèn)題的重要技巧.例1如圖291(a)3行7列小方格每一個(gè)染上紅色或藍(lán)色.試證:存在一個(gè)矩形它的四個(gè)角上的小方格顏色相同.證明由抽屜原則第1行的7個(gè)小方格至少有4個(gè)不同色不妨設(shè)為紅色(帶陰影)并在1、2、3、4列（如圖291（b））.在第1、2、3、4列（以下

2、不必再考慮第5，6，7列）中，如第2行或第3行出現(xiàn)兩個(gè)紅色小方格，則這個(gè)問(wèn)題已經(jīng)得證；如第2行和第3行每行最多只有一個(gè)紅色小方格（如圖291（c）），那么在這兩行中必出現(xiàn)四角同為藍(lán)色的矩形，問(wèn)題也得到證明.說(shuō)明：（1）在上面證明過(guò)程中除了運(yùn)用抽屜原則外，還要用到一種思考問(wèn)題的有效方法，就是逐步縮小所要討論的對(duì)象的范圍，把復(fù)雜問(wèn)題逐步化為簡(jiǎn)單問(wèn)題進(jìn)行處理的方法.（2）此例的行和列都不能再減少了.顯然只有兩行的方格盤染兩色后是不一定存在頂點(diǎn)

3、同色的矩形的.下面我們舉出一個(gè)3行6列染兩色不存在頂點(diǎn)同色矩形的例子如圖292.這說(shuō)明3行7列是染兩色存在頂點(diǎn)同色的矩形的最小方格盤了.至今染k色而存在頂點(diǎn)同色的矩形的最小方格盤是什么還不得而知.例2(第2屆全國(guó)部分省市初中數(shù)學(xué)通訊賽題)證明:用15塊大小是41的矩形瓷磚和1塊大小是22的矩形瓷磚，不能恰好鋪蓋88矩形的地面.分析將88矩形地面的一半染上一種顏色，另一半染上另一種顏色，再用41和22的矩形瓷磚去蓋，如果蓋住的兩種顏色的小

4、矩形不是一樣多，則說(shuō)明在給定條件不完滿鋪蓋不可能.證明如圖293，用間隔為兩格且與副對(duì)角線平行的斜格同色的染色方式，以黑白兩種顏色將整個(gè)地面的方格染色.顯然，地面上黑、白格各有32個(gè).每塊41的矩形磚不論是橫放還是豎蓋，且不論蓋在何處，總是占據(jù)地面上的兩個(gè)白格、兩個(gè)黑格，故15塊41的矩形磚鋪蓋后還剩兩個(gè)黑格和兩個(gè)白格.但由于與副對(duì)角線平行的斜格總是同色，而與主對(duì)角線平行的相鄰格總是異色，所以，不論怎樣放置，一塊22的矩形磚，總是蓋住三

5、黑一白或一黑三白.這說(shuō)明剩下的一塊22矩形磚無(wú)論如何蓋不住剩下的二黑二白的地面.從而問(wèn)題得證.例6(第6屆國(guó)際數(shù)學(xué)奧林匹克試題)有17位科學(xué)家其中每一個(gè)人和其他所有人的人通信他們的通信中只討論三個(gè)題目.求證:至少有三個(gè)科學(xué)家相互之間討論同一個(gè)題目.證明用平面上無(wú)三點(diǎn)共線的17個(gè)點(diǎn)A1A2…，A17分別表示17位科學(xué)家.設(shè)他們討論的題目為xyz兩位科學(xué)家討論x連紅線討論y連藍(lán)線討論z連黃線.于是只須證明以這17個(gè)點(diǎn)為頂點(diǎn)的三角形中有一同色

6、三角形.考慮以A1為端點(diǎn)的線段A1A2A1A3…，A1A17，由抽屜原則這16條線段中至少有6條同色，不妨設(shè)A1A2，A1A3，…，A1A7為紅色.現(xiàn)考查連結(jié)六點(diǎn)A2，A3，…，A7的15條線段，如其中至少有一條紅色線段，則同色（紅色）三角形已出現(xiàn)；如沒(méi)有紅色線段，則這15條線段只有藍(lán)色和黃色，由例5知一定存在以這15條線段中某三條為邊的同色三角形（藍(lán)色或黃色）.問(wèn)題得證.上述三例同屬圖論中的接姆賽問(wèn)題.在圖論中將n點(diǎn)中每?jī)牲c(diǎn)都用線段相

7、連所得的圖形叫做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é)冬令營(yíng)試題）能否把1，1，2，2，3，3，…，1986，1986這些數(shù)排成一行，使得兩個(gè)1之間夾著一個(gè)數(shù)，兩個(gè)2之間夾著兩個(gè)數(shù)，…，兩個(gè)1986

8、、之間夾著一千九百八十六個(gè)數(shù)？請(qǐng)證明你的結(jié)論.證明將19862個(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è)，其中ab=993.因此，共占白色A=A1A2=9932a個(gè).黑點(diǎn)B=B1B2=9932b個(gè)，由于ab=993（非偶數(shù)?。?/p>

9、a≠b，從而得A≠B.這與黑、白點(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è)如圖297的幾何圖形是可能的其中△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