各地中考
您現(xiàn)在的位置: 考試吧 > 2021中考 > 中考競賽 > 數(shù)學(xué)競賽 > 正文

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

考試吧提供了“22011年中招考試:《初中數(shù)學(xué)》競賽講座”,幫助考生梳理知識點(diǎn),備戰(zhàn)2011年中招考試。

  2. 線段染色和點(diǎn)染色

  下面介紹兩類重要的染色問題.

  (1) 線段染色.較常見的一類染色問題是發(fā)樣子組合數(shù)學(xué)中圖論知識的所謂“邊染色”(或稱“線段染色”),主要借助抽屜原則求解.

  例4 (1947年匈牙利數(shù)學(xué)奧林匹克試題)世界上任何六個人中,一定有3個人或者互相認(rèn)識或者互相都不認(rèn)識.

  我們不直接證明這個命題,而來看與之等價的下述命題

  例5 (1953年美國普特南數(shù)學(xué)競賽題)空間六點(diǎn),任三點(diǎn)不共線,任四點(diǎn)不共面,成對地連接它們得十五條線段,用紅色或藍(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中的六個人看成例5中六點(diǎn),兩人認(rèn)識的連紅線,不認(rèn)識的連藍(lán)線,則例4就變成了例5.例5的證明實(shí)際上用染色方法給出了例4的證明.

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

  證明 用平面上無三點(diǎn)共線的17個點(diǎn)A1,A2,…,A17分別表示17位科學(xué)家.設(shè)他們討論的題目為x,y,z,兩位科學(xué)家討論x連紅線,討論y連藍(lán)線,討論z連黃線.于是只須證明以這17個點(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)染色.先看離散的有限個點(diǎn)的情況.

  例7 (首屆全國中學(xué)生數(shù)學(xué)冬令營試題)能否把1,1,2,2,3,3,…,1986,1986這些數(shù)排成一行,使得兩個1之間夾著一個數(shù),兩個2之間夾著兩個數(shù),…,兩個1986、之間夾著一千九百八十六個數(shù)?請證明你的結(jié)論.

  證明 將1986×2個位置按奇數(shù)位著白色,偶數(shù)位著黑色染色,于是黑白點(diǎn)各有1986個.

  現(xiàn)令一個偶數(shù)占據(jù)一個黑點(diǎn)和一個白色,同一個奇數(shù)要么都占黑點(diǎn),要么都占白點(diǎn).于是993個偶數(shù),占據(jù)白點(diǎn)A1=993個,黑色B1=993個.

  993個奇數(shù),占據(jù)白點(diǎn)A2=2a個,黑點(diǎn)B2=2b個,其中a+b=993.

  因此,共占白色A=A1+A2=993+2a個.

  黑點(diǎn)B=B1+B2=993+2b個,

  由于a+b=993(非偶數(shù)!)∴a≠b,從而得A≠B.這與黑、白點(diǎn)各有1986個矛盾.

  故這種排法不可能.

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

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

  證明 作出一個如圖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)時,又如果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),這時CG是端點(diǎn)同色的單位線段.證畢.

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

  相關(guān)推薦:

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

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

0
收藏該文章
文章搜索
國家 北京 天津 上海 重慶
河北 山西 遼寧 吉林 江蘇
浙江 安徽 福建 江西 山東
河南 湖北 湖南 廣東 廣西
海南 四川 貴州 云南 西藏
陜西 甘肅 寧夏 青海 新疆
黑龍江 內(nèi)蒙古 更多
中考欄目導(dǎo)航
版權(quán)聲明:如果中考網(wǎng)所轉(zhuǎn)載內(nèi)容不慎侵犯了您的權(quán)益,請與我們聯(lián)系800@exam8.com,我們將會及時處理。如轉(zhuǎn)載本中考網(wǎng)內(nèi)容,請注明出處。
領(lǐng)
免費(fèi)復(fù)習(xí)資料
最新中考資訊
文章責(zé)編:魏超杰