2. 線段染色和點(diǎn)染色
下面介紹兩類(lèi)重要的染色問(wèn)題.
(1) 線段染色.較常見(jiàn)的一類(lèi)染色問(wèn)題是發(fā)樣子組合數(shù)學(xué)中圖論知識(shí)的所謂“邊染色”(或稱(chēng)“線段染色”),主要借助抽屜原則求解.
例4 (1947年匈牙利數(shù)學(xué)奧林匹克試題)世界上任何六個(gè)人中,一定有3個(gè)人或者互相認(rèn)識(shí)或者互相都不認(rèn)識(shí).
我們不直接證明這個(gè)命題,而來(lái)看與之等價(jià)的下述命題
例5 (1953年美國(guó)普特南數(shù)學(xué)競(jìng)賽題)空間六點(diǎn),任三點(diǎn)不共線,任四點(diǎn)不共面,成對(duì)地連接它們得十五條線段,用紅色或藍(lán)色染這些線段(一條線段只染一種顏色).求證:無(wú)論怎樣染,總存在同色三角形.
證明 設(shè)A、B、C、D、E、F是所給六點(diǎn).考慮以A為端點(diǎn)的線段AB、AC、AD、AE、AF,由抽屜原則這五條線段中至少有三條顏色相同,不妨設(shè)就是AB、AC、AD,且它們都染成紅色.再來(lái)看△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屆國(guó)際數(shù)學(xué)奧林匹克試題)有17位科學(xué)家,其中每一個(gè)人和其他所有人的人通信,他們的通信中只討論三個(gè)題目.求證:至少有三個(gè)科學(xué)家相互之間討論同一個(gè)題目.
證明 用平面上無(wú)三點(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);如沒(méi)有紅色線段,則這15條線段只有藍(lán)色和黃色,由例5知一定存在以這15條線段中某三條為邊的同色三角形(藍(lán)色或黃色).問(wèn)題得證.
上述三例同屬圖論中的接姆賽問(wèn)題.在圖論中,將n點(diǎn)中每?jī)牲c(diǎn)都用線段相連所得的圖形叫做n點(diǎn)完全圖,記作kn.這些點(diǎn)叫做“頂點(diǎn)”,這些線段叫做“邊”.現(xiàn)在我們分別用圖論的語(yǔ)言來(lái)敘述例5、例6.
定理1 若在k6中,任染紅、藍(lán)兩色,則必有一只同色三角形.
定理2 在k17中,任染紅、藍(lán)、黃三角,則必有一只同色三角形.
(2)點(diǎn)染色.先看離散的有限個(gè)點(diǎn)的情況.
例7 (首屆全國(guó)中學(xué)生數(shù)學(xué)冬令營(yíng)試題)能否把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è),也可以是無(wú)限個(gè),這時(shí)染色問(wèn)題總是與相應(yīng)的幾何問(wèn)題聯(lián)系在一起的.
例8 對(duì)平面上一個(gè)點(diǎn),任意染上紅、藍(lán)、黑三種顏色中的一種.證明:平面內(nèi)存在端點(diǎn)同色的單位線段.
證明 作出一個(gè)如圖29-7的幾何圖形是可能的,其中△ABD、△CBD、△AEF、△GEF都是邊長(zhǎng)為1的等邊三角形,CG=1.不妨設(shè)A點(diǎn)是紅色,如果B、E、D、F中有紅色,問(wèn)題顯然得證.當(dāng)B、E、D、F都為藍(lán)點(diǎn)或黃點(diǎn)時(shí),又如果B和D或E和F同色,問(wèn)題也得證.現(xiàn)設(shè)B和D異色E和F異色,在這種情況下,如果C或G為黃色或藍(lán)點(diǎn),則CB、CD、GE、GF中有兩條是端點(diǎn)同色的單位線段,問(wèn)題也得證.不然的話,C、G均為紅點(diǎn),這時(shí)CG是端點(diǎn)同色的單位線段.證畢.
還有一類(lèi)較難的對(duì)區(qū)域染色的問(wèn)題,就不作介紹了.
相關(guān)推薦:·2021中考語(yǔ)文閱讀理解最全的33套答題公式 (2020-11-10 17:20:05)
·2020中考生物知識(shí)點(diǎn)結(jié)構(gòu)圖分類(lèi)整理:健康的生活 (2019-11-8 14:54:53)
·2020中考生物知識(shí)點(diǎn)結(jié)構(gòu)圖分類(lèi)整理:生物技術(shù) (2019-11-8 14:53:20)
·2020中考生物知識(shí)點(diǎn)結(jié)構(gòu)圖分類(lèi)整理:生物的多樣性 (2019-11-8 14:50:27)
·2020中考生物知識(shí)點(diǎn)結(jié)構(gòu)圖分類(lèi)整理:生物的生殖發(fā)育與遺 (2019-11-8 14:48:17)
2022年海南中考地理真題及答案已公布
2022年海南中考生物真題及答案已公布
2022年海南中考?xì)v史真題及答案已公布
2022年海南中考政治真題及答案已公布
2022年海南中考化學(xué)真題及答案已公布
2022年海南中考物理真題及答案已公布
2022年海南中考英語(yǔ)真題及答案已公布
2022年海南中考數(shù)學(xué)真題及答案已公布
2022年海南中考語(yǔ)文真題及答案已公布
2022年福建漳州中考成績(jī)查詢(xún)?nèi)肟谝验_(kāi)通
2022廣東汕尾中考成績(jī)7月13日公布
2022年黑龍江齊齊哈爾中考成績(jī)查詢(xún)?nèi)肟谝?/a>
2022年黑龍江哈爾濱中考成績(jī)查詢(xún)?nèi)肟谝验_(kāi)
2022年安徽亳州中考成績(jī)7月2日公布
2022年安徽銅陵中考成績(jī)查詢(xún)?nèi)肟谝验_(kāi)通 點(diǎn)
2022年福建廈門(mén)中考成績(jī)查詢(xún)?nèi)肟谝验_(kāi)通 點(diǎn)
2022寧夏銀川中考成績(jī)查詢(xún)?nèi)肟谝验_(kāi)通 點(diǎn)擊
2022年吉安市中考成績(jī)查詢(xún)?nèi)肟谝验_(kāi)通 點(diǎn)擊
國(guó)家 | 北京 | 天津 | 上海 | 重慶 |
河北 | 山西 | 遼寧 | 吉林 | 江蘇 |
浙江 | 安徽 | 福建 | 江西 | 山東 |
河南 | 湖北 | 湖南 | 廣東 | 廣西 |
海南 | 四川 | 貴州 | 云南 | 西藏 |
陜西 | 甘肅 | 寧夏 | 青海 | 新疆 |
黑龍江 | 內(nèi)蒙古 | 更多 |
·執(zhí)業(yè)醫(yī)師考試培訓(xùn) 試聽(tīng) ·經(jīng)濟(jì)師考試培訓(xùn) 試聽(tīng)
·執(zhí)業(yè)藥師考試培訓(xùn) 試聽(tīng) ·報(bào)關(guān)員考試培訓(xùn) 試聽(tīng)
·銀行從業(yè)考試培訓(xùn) 試聽(tīng) ·會(huì)計(jì)證考試培訓(xùn) 試聽(tīng)
·證券從業(yè)考試培訓(xùn) 試聽(tīng) ·華圖公務(wù)員培訓(xùn) 試聽(tīng)
·二級(jí)建造師考試培訓(xùn) 試聽(tīng) ·公務(wù)員培訓(xùn) 網(wǎng)校 試聽(tīng)
·一級(jí)建造師考試培訓(xùn) 試聽(tīng) ·結(jié)構(gòu)師考試培訓(xùn) 試聽(tīng)
·注冊(cè)建筑師考試培訓(xùn) 試聽(tīng) ·造價(jià)師考試培訓(xùn) 試聽(tīng)
·質(zhì)量資格考試培訓(xùn) 試聽(tīng) ·咨詢(xún)師考試培訓(xùn) 試聽(tīng)
·衛(wèi)生職稱(chēng)考試培訓(xùn) 試聽(tīng) ·監(jiān)理師考試培訓(xùn) 試聽(tīng)
·報(bào)關(guān)員考試培訓(xùn) 試聽(tīng) ·經(jīng)濟(jì)師考試培訓(xùn) 試聽(tīng)
·銀行從業(yè)考試培訓(xùn) 試聽(tīng) ·會(huì)計(jì)證考試培訓(xùn) 試聽(tīng)
·證券從業(yè)考試培訓(xùn) 試聽(tīng) ·注冊(cè)會(huì)計(jì)師培訓(xùn) 試聽(tīng)
·期貨從業(yè)考試培訓(xùn) 試聽(tīng) ·統(tǒng)計(jì)師考試培訓(xùn) 試聽(tīng)
·國(guó)際商務(wù)師考試培訓(xùn) 試聽(tīng) ·稅務(wù)師考試培訓(xùn) 試聽(tīng)
·人力資源師考試培訓(xùn) 試聽(tīng) ·評(píng)估師考試培訓(xùn) 試聽(tīng)
·管理咨詢(xún)師考試培訓(xùn) 試聽(tīng) ·審計(jì)師考試培訓(xùn) 試聽(tīng)
·報(bào)檢員考試培訓(xùn) 試聽(tīng) ·高級(jí)會(huì)計(jì)師考試培訓(xùn) 試聽(tīng)
·外銷(xiāo)員考試培訓(xùn) 試聽(tīng) ·公務(wù)員 試聽(tīng) 教育門(mén)戶(hù)
·二級(jí)建造師考試培訓(xùn) 試聽(tīng) ·招標(biāo)師考試培訓(xùn) 試聽(tīng)
·造價(jià)師考試培訓(xùn) 試聽(tīng) ·物業(yè)管理師考試培訓(xùn) 試聽(tīng)
·監(jiān)理師考試培訓(xùn) 試聽(tīng) ·設(shè)備監(jiān)理師考試培訓(xùn) 試聽(tīng)
·安全師考試培訓(xùn) 試聽(tīng) ·巖土工程師考試培訓(xùn) 試聽(tīng)
·咨詢(xún)師考試培訓(xùn) 試聽(tīng) ·投資項(xiàng)目管理師培訓(xùn) 試聽(tīng)
·結(jié)構(gòu)師考試培訓(xùn) 試聽(tīng) ·公路監(jiān)理師考試培訓(xùn) 試聽(tīng)
·建筑師考試培訓(xùn) 試聽(tīng) ·衛(wèi)生資格考試培訓(xùn) 試聽(tīng)
·質(zhì)量資格考試培訓(xùn) 試聽(tīng) ·執(zhí)業(yè)藥師考試培訓(xùn) 試聽(tīng)
·造價(jià)員考試培訓(xùn) 試聽(tīng) ·執(zhí)業(yè)醫(yī)師考試培訓(xùn) 試聽(tīng)