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

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

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

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

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

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

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

7、連所得的圖形叫做n點完全圖記作kn.這些點叫做“頂點”，這些線段叫做“邊”.現(xiàn)在我們分別用圖論的語言來敘述例5、例6.定理1若在k6中，任染紅、藍(lán)兩色，則必有一只同色三角形.定理2在k17中任染紅、藍(lán)、黃三角，則必有一只同色三角形.（2）點染色.先看離散的有限個點的情況.例7（首屆全國中學(xué)生數(shù)學(xué)冬令營試題）能否把1，1，2，2，3，3，…，1986，1986這些數(shù)排成一行，使得兩個1之間夾著一個數(shù)，兩個2之間夾著兩個數(shù)，…，兩個1986

8、、之間夾著一千九百八十六個數(shù)？請證明你的結(jié)論.證明將19862個位置按奇數(shù)位著白色，偶數(shù)位著黑色染色，于是黑白點各有1986個.現(xiàn)令一個偶數(shù)占據(jù)一個黑點和一個白色，同一個奇數(shù)要么都占黑點，要么都占白點.于是993個偶數(shù)，占據(jù)白點A1=993個，黑色B1=993個.993個奇數(shù)，占據(jù)白點A2=2a個，黑點B2=2b個，其中ab=993.因此，共占白色A=A1A2=9932a個.黑點B=B1B2=9932b個，由于ab=993（非偶數(shù)?。?/p>

9、a≠b，從而得A≠B.這與黑、白點各有1986個矛盾.故這種排法不可能.“點”可以是有限個，也可以是無限個，這時染色問題總是與相應(yīng)的幾何問題聯(lián)系在一起的.例8對平面上一個點，任意染上紅、藍(lán)、黑三種顏色中的一種.證明:平面內(nèi)存在端點同色的單位線段.證明作出一個如圖297的幾何圖形是可能的其中△ABD、△CBD、△AEF、△GEF都是邊長為1的等邊三角形，CG=1.不妨設(shè)A點是紅色，如果B、E、D、F中有紅色，問題顯然得證.當(dāng)B、E、D、F