2011年中招考試：《初中數(shù)學(xué)》競賽講座(14)

　　2. 線段染色和點(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é)競賽題)空間六點(diǎn)，任三點(diǎn)不共線，任四點(diǎn)不共面，成對(duì)地連接它們得十五條線段，用紅色或藍(lán)色染這些線段(一條線段只染一種顏色).求證:無論怎樣染,總存在同色三角形.

　　證明 設(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)了.總之,不論在哪種情況下,都存在同色三角形.

　　如果將例4中的六個(gè)人看成例5中六點(diǎn),兩人認(rèn)識(shí)的連紅線,不認(rèn)識(shí)的連藍(lán)線,則例4就變成了例5.例5的證明實(shí)際上用染色方法給出了例4的證明.

　　例6 (第6屆國際數(shù)學(xué)奧林匹克試題)有17位科學(xué)家,其中每一個(gè)人和其他所有人的人通信,他們的通信中只討論三個(gè)題目.求證:至少有三個(gè)科學(xué)家相互之間討論同一個(gè)題目.

　　證明 用平面上無三點(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的15條線段，如其中至少有一條紅色線段，則同色(紅色)三角形已出現(xiàn);如沒有紅色線段，則這15條線段只有藍(lán)色和黃色，由例5知一定存在以這15條線段中某三條為邊的同色三角形(藍(lán)色或黃色).問題得證.

　　上述三例同屬圖論中的接姆賽問題.在圖論中,將n點(diǎn)中每兩點(diǎn)都用線段相連所得的圖形叫做n點(diǎn)完全圖,記作kn.這些點(diǎn)叫做“頂點(diǎn)”，這些線段叫做“邊”.現(xiàn)在我們分別用圖論的語言來敘述例5、例6.

　　定理1 若在k6中，任染紅、藍(lán)兩色，則必有一只同色三角形.

　　定理2 在k17中,任染紅、藍(lán)、黃三角，則必有一只同色三角形.

　　(2)點(diǎn)染色.先看離散的有限個(gè)點(diǎn)的情況.

　　例7 (首屆全國中學(xué)生數(shù)學(xué)冬令營試題)能否把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(非偶數(shù)!)∴a≠b，從而得A≠B.這與黑、白點(diǎn)各有1986個(gè)矛盾.

　　故這種排法不可能.

　　“點(diǎn)”可以是有限個(gè)，也可以是無限個(gè)，這時(shí)染色問題總是與相應(yīng)的幾何問題聯(lián)系在一起的.

　　例8 對(duì)平面上一個(gè)點(diǎn)，任意染上紅、藍(lán)、黑三種顏色中的一種.證明:平面內(nèi)存在端點(diǎn)同色的單位線段.

　　證明 作出一個(gè)如圖29-7的幾何圖形是可能的,其中△ABD、△CBD、△AEF、△GEF都是邊長為1的等邊三角形，CG=1.不妨設(shè)A點(diǎn)是紅色，如果B、E、D、F中有紅色，問題顯然得證.當(dāng)B、E、D、F都為藍(lán)點(diǎn)或黃點(diǎn)時(shí)，又如果B和D或E和F同色，問題也得證.現(xiàn)設(shè)B和D異色E和F異色,在這種情況下,如果C或G為黃色或藍(lán)點(diǎn),則CB、CD、GE、GF中有兩條是端點(diǎn)同色的單位線段，問題也得證.不然的話,C、G均為紅點(diǎn)，這時(shí)CG是端點(diǎn)同色的單位線段.證畢.

　　還有一類較難的對(duì)區(qū)域染色的問題，就不作介紹了.

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

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