初二.染色問題與染色方法

1、148[文件]sxjisck0003.doc[科目]數(shù)學(xué)[關(guān)鍵詞]初二染色問題染色方法[標(biāo)題]染色問題與染色方法[內(nèi)容]染色問題與染色方法染色問題與染色方法1小方格染色問題最簡(jiǎn)單的染色問題是從一種民間游戲中發(fā)展起來的方格盤上的染色問題.解決這類問題的方法后來又發(fā)展成為解決方格盤鋪蓋問題的重要技巧.例1如圖291(a)3行7列小方格每一個(gè)染上紅色或藍(lán)色.試證:存在一個(gè)矩形它的四個(gè)角上的小方格顏色相同.證明由抽屜原則第1行的7個(gè)小方格至少有

2、4個(gè)不同色不妨設(shè)為紅色(帶陰影)并在1、2、3、4列（如圖291（b））.在第1、2、3、4列（以下不必再考慮第5，6，7列）中，如第2行或第3行出現(xiàn)兩個(gè)紅色小方格，則這個(gè)問題已經(jīng)得證；如第2行和第3行每行最多只有一個(gè)紅色小方格（如圖291（c）），那么在這兩行中必出現(xiàn)四角同為藍(lán)色的矩形，問題也得到證明.說明：（1）在上面證明過程中除了運(yùn)用抽屜原則外，還要用到一種思考問題的有效方法，就是逐步縮小所要討論的對(duì)象的范圍，把復(fù)雜問題逐步化為簡(jiǎn)

3、單問題進(jìn)行處理的方法.（2）此例的行和列都不能再減少了.顯然只有兩行的方格盤染兩色后是不一定存在頂點(diǎn)同色的矩形的.下面我們舉出一個(gè)3行6列染兩色不存在頂點(diǎn)同色矩形的例子如圖292.這說明3行7列是染兩色存在頂點(diǎn)同色的矩形的最小方格盤了.至今染k色而存在頂點(diǎn)同色的矩形的最小方格盤是什么還不得而知.例2(第2屆全國部分省市初中數(shù)學(xué)通訊賽題)證明:用15塊大小是41的矩形瓷磚和1塊大小是22的矩形瓷磚，不能恰好鋪蓋88矩形的地面.1502線段

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

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