競(jìng)賽講座14

　　-染色問(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))，那么在這兩行中必出現(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塊大小是2×2的矩形瓷磚，不能恰好鋪蓋8×8矩形的地面.

　　分析 將8×8矩形地面的一半染上一種顏色，另一半染上另一種顏色，再用4×1和2×2的矩形瓷磚去蓋，如果蓋住的兩種顏色的小矩形不是一樣多，則說(shuō)明在給定條件不完滿(mǎn)鋪蓋不可能.

　　證明 如圖29-3，用間隔為兩格且與副對(duì)角線(xiàn)平行的斜格同色的染色方式，以黑白兩種顏色將整個(gè)地面的方格染色.顯然，地面上黑、白格各有32個(gè).

　　每塊4×1的矩形磚不論是橫放還是豎蓋，且不論蓋在何處，總是占據(jù)地面上的兩個(gè)白格、兩個(gè)黑格，故15塊4×1的矩形磚鋪蓋后還剩兩個(gè)黑格和兩個(gè)白格.但由于與副對(duì)角線(xiàn)平行的斜格總是同色，而與主對(duì)角線(xiàn)平行的相鄰格總是異色，所以，不論怎樣放置，一塊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ù)，不妨設(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ù).

　　2011年中考數(shù)學(xué)備考輔導(dǎo)：選擇題精選匯總

　　名師解讀南京2011年中考數(shù)學(xué)命題趨勢(shì)