簡單的染色問題

1、14 / 14簡單的染色問題哈師大附中 趙巖在我們美麗的地球上，有60多億人口，任何六個(gè)人聚在一起，或者有三個(gè)人彼此相識(shí)，或者有三個(gè)人彼此不相識(shí)。你相信嗎？那就先讓我們來作個(gè)游戲！ 規(guī)則：正六邊形的六個(gè)頂點(diǎn)，兩游戲者每次可隨意選用紅或藍(lán)色的筆，輪流選擇其中的兩點(diǎn)連線，誰第一個(gè)被迫畫成一個(gè)同色的三角形（紅色或白色），他就是失敗者 這個(gè)游戲是否一定能分出勝負(fù)呢？與先下后下是否有關(guān)？ 抽象數(shù)學(xué)問題：把六個(gè)點(diǎn)（任意三點(diǎn)不共線）的連線染兩色，至少會(huì)出現(xiàn)一個(gè)同色三角形ADBC證明：任取一點(diǎn)A，那么由點(diǎn)A引出的5條邊中，由抽屜原理，至少有三條是同色的，不妨設(shè)AB、AC、AD是藍(lán)色的，如圖所示考察BC、BD、

2、CD三條邊，若這三條邊中有一條是藍(lán)色的，則與A形成一個(gè)藍(lán)色三角形；若這三條邊都是紅色的，則三角形BCD為一個(gè)紅色三角形 “任何六個(gè)人聚在一起，或者有三個(gè)人彼此相識(shí)，或者有三個(gè)人彼此不相識(shí)”這樣一個(gè)著名的實(shí)際問題也就迎刃而解 1928年，在英國倫敦?cái)?shù)學(xué)會(huì)的一次學(xué)術(shù)會(huì)議上，年僅24歲的年輕數(shù)學(xué)家弗蘭克·普拉東·拉姆賽（Frank Plumpton Ramsey）證明了一個(gè)定理：如果某一集合（如點(diǎn)集）中事物的數(shù)量足夠多，且每對(duì)事物間都存在一定數(shù)量的關(guān)系（如各種顏色的邊）中的一種，那么必定存在一個(gè)包含若干數(shù)目事物的子集（如三點(diǎn)集），其中每對(duì)事物間也存在同樣的關(guān)系（如同色三角形） 這

3、個(gè)定理稱為拉姆賽定理，告訴我們：如果平面上的點(diǎn)數(shù)足夠多，且每對(duì)點(diǎn)間的線（邊）或染紅色或染藍(lán)色，那么必定存在一個(gè)包含3個(gè)點(diǎn)的子集，他們之間的邊同色，即包含一個(gè)同色三角形如果我們將剛才的六點(diǎn)染色游戲繼續(xù)下去，染完所有的線段，同色三角形最少出現(xiàn)了幾個(gè)？這是偶然嗎？恭喜你！答對(duì)了，2個(gè)！在六點(diǎn)（任意三點(diǎn)不共線）染色游戲中，必有兩個(gè)同色三角形證明：方法一：為方便敘述，我們把平面上有個(gè)點(diǎn)，每兩點(diǎn)都有連線的圖稱為階完全圖，記作由拉姆賽定理知把邊染紅、藍(lán)兩色，必出現(xiàn)一個(gè)同色三角形，不妨設(shè)這個(gè)三角形是紅色的ABFCDAE 現(xiàn)考慮ABC以外的點(diǎn)D、E、F，由D引出的五條邊中，由抽屜原理，至少有三條邊是同色的，除了

4、D與A、B、C所連的邊是藍(lán)色的情形以外，其余情形均可仿照結(jié)前面的證明得到一個(gè)同色三角形；同理，E、F引出的邊也有同樣的結(jié)論于是，只剩下如圖情形，即D、E、F與ABC的三頂點(diǎn)連線均是藍(lán)色這時(shí)，三角形DEF或者是紅色三角形，或者與原來的藍(lán)邊形成一個(gè)藍(lán)色三角形方法二（算兩次）： 考慮自同一點(diǎn)引出的兩條邊，如果他們顏色相同，就稱他們組成一個(gè)“同色角”，設(shè)自點(diǎn)A引出r條紅邊，5r條白邊，則自A點(diǎn)引出的同色角共有（）個(gè)，易知當(dāng)r2或3時(shí)最小，最小值為4，所以該六點(diǎn)圖中至少有6×424個(gè)同色角；另一方面，每個(gè)同色三角形中有3個(gè)同色角，每個(gè)邊不全同色的三角形中只有1個(gè)同色角設(shè)同色三角形有個(gè)，則不同色

5、三角形有（）個(gè)，因此，同色角共有個(gè)綜上，從而，如果減少一點(diǎn)，做五點(diǎn)（任意三點(diǎn)不共線）染色游戲是否一定能分出勝負(fù)呢？如出現(xiàn)平局，平局的圖形是什么樣的呢？讀者不妨動(dòng)手一試，在五點(diǎn)染色游戲中，或者必出現(xiàn)一個(gè)同色三角形，或者必出現(xiàn)一個(gè)同色五邊形（首尾順次連接即可）如將上述一類問題推廣，可在哪幾方面進(jìn)行變化？請(qǐng)讀者思考例1在2色完全圖中，至少存在一個(gè)紅色三角形或一個(gè)藍(lán)色四邊形證明：如果中有一個(gè)點(diǎn)引出至少條紅邊，不妨設(shè)為紅邊，這時(shí)四個(gè)點(diǎn)所成的中或者每條邊都是藍(lán)色，或者至少有一條邊為紅色在后一種情況，設(shè)紅邊為，則為紅色三角形如果中每個(gè)點(diǎn)引出的紅邊少于4條，那么每點(diǎn)至少引出5條藍(lán)邊由于藍(lán)邊的總數(shù)的2倍，所以，

6、藍(lán)邊的總數(shù)的2倍，從而至少有一點(diǎn)引出6條藍(lán)邊設(shè)為藍(lán)邊，這時(shí)所成的中必有一個(gè)同色三角形如果是紅色三角形，結(jié)論成立；如果是藍(lán)色三角形，那么它的三個(gè)頂點(diǎn)與構(gòu)成藍(lán)色的例2（2005西部）設(shè)個(gè)新生中，任意3個(gè)人中有2個(gè)人互相認(rèn)識(shí)，任意4個(gè)人中有2個(gè)人互不認(rèn)識(shí)，試求的最大值解：當(dāng)時(shí)，如圖所示的例子滿足要求，其中表示8個(gè)學(xué)生，紅色表示認(rèn)識(shí)下設(shè)個(gè)學(xué)生滿足題設(shè)要求，證明為此先證明如下兩種情況不可能出現(xiàn)（1）若某人至少認(rèn)識(shí)6個(gè)人，記為，由拉姆賽定理，這6個(gè)人中或者有3個(gè)人彼此不相識(shí)，與已知任意3個(gè)人中有2個(gè)人認(rèn)識(shí)矛盾；或者有3個(gè)人彼此相識(shí)，這時(shí)與這3個(gè)人共4個(gè)人互相認(rèn)識(shí)與已知任意4個(gè)人中有2個(gè)人互不認(rèn)識(shí)矛盾！（2

7、）若至多認(rèn)識(shí)個(gè)人，則剩下至少4個(gè)人均與互不認(rèn)識(shí)，從而與這4個(gè)人兩兩相識(shí)，矛盾！其次，當(dāng)時(shí)，（1）與（2）必有一種情況出現(xiàn)，故此時(shí)不滿足要求當(dāng)時(shí)，要使（1）與（2）均不出現(xiàn)，則此時(shí)每個(gè)人恰好認(rèn)識(shí)其他5個(gè)人于是，這9個(gè)人產(chǎn)生的朋友對(duì)的數(shù)目為，矛盾！綜上，所求的最大值為8例2（第六屆IMO）17位學(xué)者，每一位都給其余的人寫一封信，信的內(nèi)容是討論三個(gè)問題中的一個(gè)而且兩個(gè)人互相通信所討論的是同一個(gè)問題。證明：至少有三位學(xué)者，他們之間通信所討論的是同一個(gè)問題證明：作完全圖，它的17個(gè)點(diǎn)分別表示17位科學(xué)家.設(shè)他們討論的題目為,兩位科學(xué)家討論連紅線,討論連藍(lán)線,討論連黃線.于是只須證明這個(gè)中有一同色三角形.

8、任取一點(diǎn)，自引出的邊共16條，因而一定有條邊同色，不妨設(shè)為紅色. 構(gòu)成的完全圖中，如果有一條邊也是紅色，則為紅色三角形；如果這個(gè)中沒有紅色邊，只有藍(lán)色和黃色，由拉姆賽定理知一定存同色三角形（藍(lán)色或黃色）.例3兩個(gè)航空公司為十個(gè)城市通航，使得任意兩個(gè)城市之間恰有一個(gè)公司開設(shè)直達(dá)航班的往返服務(wù)，證明：至少有一個(gè)公司能提供兩個(gè)不相交的旅游圈，每圈可游覽奇數(shù)個(gè)城市證明： 在完全圖中10個(gè)頂點(diǎn)中取出6個(gè)點(diǎn)，由拉姆賽定理知，這6點(diǎn)組成的的邊染兩色至少有一個(gè)同色三角形，不妨記為 由余下的7個(gè)點(diǎn)組成的中也至少存在一個(gè)同色三角形，記為 當(dāng)然，與是沒有公共點(diǎn)的，如果他們同色，則結(jié)論成立因此僅需考慮不同色的情形 不

9、妨設(shè)為紅色三角形，而為藍(lán)色三角形，這兩個(gè)三角形之間還有9條邊，這9條邊染兩色，至少有5條邊是同色的，不妨設(shè)有5條藍(lán)邊 因此，在中，至少有一個(gè)點(diǎn)，它引出兩條藍(lán)邊，不妨設(shè)是藍(lán)邊于是我們得到紅色和藍(lán)色于是除了這兩個(gè)紅、藍(lán)三角形（和）外，還剩5個(gè)點(diǎn)，我們把這5個(gè)點(diǎn)記作（其中有一個(gè)點(diǎn)曾經(jīng)稱為） 現(xiàn)在考慮由所成的，若這個(gè)中有同色三角形，則此三角形和、都無公共點(diǎn)，且必與其中之一同色，結(jié)論成立；若這個(gè)中無同色三角形，由前面的5點(diǎn)染色游戲知，必有一個(gè)同色五邊形，它與、無公共點(diǎn)于是出現(xiàn)兩個(gè)同色奇數(shù)圈 由于染色問題主要涉及集合元素的分類，與自然數(shù)密切相關(guān)，因此在處理手法上不能僅限于上面提到的，數(shù)學(xué)歸納法也就不乏用武

10、之地了例4（第29屆俄羅斯數(shù)學(xué)奧林匹克）某國有個(gè)城市，每兩個(gè)城市之間或者有公路，或者有鐵路相連一個(gè)旅行者希望到達(dá)每個(gè)城市恰好一次，并且最終回到他所出發(fā)的城市證明：該旅行者可以挑選一個(gè)城市作為出發(fā)點(diǎn)，不但能夠?qū)崿F(xiàn)他的愿望，而且途中至多變換一次交通工具的種類證明： 問題可以轉(zhuǎn)化為，給定一個(gè)完全圖，對(duì)它的邊染兩種不同的顏色證明，從中可以找到一個(gè)經(jīng)過所有頂點(diǎn)的圈，該圈至多可以分為兩個(gè)各自同色的部分 對(duì)N用數(shù)學(xué)歸納法 當(dāng)時(shí)，命題顯然成立； 假設(shè)時(shí)命題成立，考慮的情形先從所考察的圖中去掉一個(gè)頂點(diǎn)M及所有從它出發(fā)的邊由歸納假設(shè)知，在剩下的完全圖中存在一個(gè)經(jīng)過所有頂點(diǎn)的圈該圈之多可以分為兩個(gè)各自同色的部分下面

11、分兩種情形討論：（1）該圈上的所有邊全都同色依次將圈上的頂點(diǎn)記為從中去掉邊，然后將頂點(diǎn)分別與、相連，所得的圈即符合要求（2）該圈上的所有邊不全同色將頂點(diǎn)編號(hào)，使得對(duì)某個(gè)頂點(diǎn)，圈上由到的部分為一種顏色（紅色），為另一種顏色（藍(lán)色）只要觀察邊的顏色：如果該邊為紅色，則圈為所求；如果該邊為藍(lán)色，則圈為所求 這就表明，對(duì)于命題也成立例5（第30屆俄羅斯數(shù)學(xué)奧林匹克）某國有若干個(gè)城市和個(gè)不同的航空公司任意個(gè)城市之間，或者有條屬于某個(gè)航空公司的雙向的直飛航線連接，或者沒有航線連接已知任意條同一公司的航線都有公共的端點(diǎn)證明：可以將所有的城市分為個(gè)組，使得任意個(gè)屬于同一組的城市之間都沒有航線相連證明：對(duì)進(jìn)行數(shù)

12、學(xué)歸納當(dāng)時(shí)，沒有航空公司，結(jié)論顯然成立 作一個(gè)凸多邊形，其中的頂點(diǎn)為該國的城市，邊為航線。分別以表示各個(gè)航空公司的航線所對(duì)應(yīng)的邊的集合，由已知條件，易知對(duì)于每個(gè)集合或者為三角形，或者為“花”，即具有一個(gè)公共頂點(diǎn)的若干條邊 如果存在一個(gè)集合是以頂點(diǎn)A為公共頂點(diǎn)的“花”，那么，就從圖中去掉頂點(diǎn)A和所有由A所連出的邊于是在剩下的圖中只有家航空公司的航線根據(jù)歸納假設(shè)，可以把所有的頂點(diǎn)分成組，使得任意任意個(gè)屬于同一組的城市之間都沒有航線相連再把A作為第組即可 如果所有的都是三角形，此時(shí)圖中恰好有條邊，我們只需將圖中的頂點(diǎn)分為盡可能少的組，使得任意個(gè)屬于同一組的頂點(diǎn)之間都沒有邊相連即可否則假設(shè)所分出的組為

13、，且注意到，此時(shí)在任何兩個(gè)組和之間，都一定有某條邊聯(lián)結(jié)和中的某個(gè)頂點(diǎn)，若不然，就可以把兩個(gè)組并成一組從而，該圖中至少有條邊，這樣一來，就有，矛盾 所以，原結(jié)論成立平面幾何選講反演變換基礎(chǔ)知識(shí)一、定義1設(shè)是平面上的一個(gè)定點(diǎn)，是一個(gè)非零常數(shù)如果平面的一個(gè)變換，使得對(duì)于平面上任意異于的點(diǎn)與其對(duì)應(yīng)點(diǎn)之間，恒有（1）三點(diǎn)共線；（2）則這個(gè)變換稱為平面的一個(gè)反演變換，記做其中，定點(diǎn)稱為反演中心，常數(shù)稱為反演冪，點(diǎn)稱為點(diǎn)的反點(diǎn)2在反演變換下，如果平面的圖形變?yōu)閳D形，則稱圖形是圖形關(guān)于反演變換的反形反演變換的不動(dòng)點(diǎn)稱為自反點(diǎn)，而反演變換的不變圖形則稱為自反圖形3設(shè)兩條曲線相交于點(diǎn)，、分別是曲線在點(diǎn)處的切線（如

14、果存在），則與的交角稱為曲線在點(diǎn)處的交角；如果兩切線重合，則曲線在點(diǎn)處的交角為特別地，如果兩圓交于點(diǎn)，那么過點(diǎn)作兩圓的切線，則切線的交角稱為兩圓的交角當(dāng)兩圓的交角為時(shí)，稱為兩圓正交；如果直線與圓相交，那么過交點(diǎn)作圓的切線，則切線與直線的交角就是直線與圓的交角當(dāng)這個(gè)交角為時(shí)，稱為直線與圓正交二、定理定理1在反演變換下，不共線的兩對(duì)互反點(diǎn)是共圓的四點(diǎn)定理2在反演變換下，設(shè)兩點(diǎn)（均不同于反演中心）的反點(diǎn)分別為，則有定理3在反演變換下，過反演中心的直線不變定理4在反演變換下，不過反演中心的直線的反形是過反演中心的圓；過反演中心的圓的反形是不過反演中心的直線定理5在反演變換下，不過反演中心的圓的反形仍是

15、不過反演中心的圓定理6在反演變換下，兩條曲線在交點(diǎn)處的交角大小保持不變，但方向相反定理7如果兩圓或一圓一直線相切于反演中心，則其反形是兩條平行直線；如果兩圓或一圓一直線相切于非反演中心，則其反形（兩圓或一圓一直線）相切定理8如果兩直線平行，則其反形（兩圓或一圓一直線）相切于反演中心典型例題一、證明點(diǎn)共線例1的內(nèi)切圓與邊、分別相切于點(diǎn)、，設(shè)、分別是、的中點(diǎn)求證：的外心、內(nèi)心與的外心三點(diǎn)共線證明：如圖，設(shè)的內(nèi)心為，內(nèi)切圓半徑為以內(nèi)心為反演中心，內(nèi)切圓為反演圓作反演變換，則、的反點(diǎn)分別為、，因而的反形是的外接圓故的外心、內(nèi)心和的外心三點(diǎn)共線二、證明線共點(diǎn) 例2四邊形內(nèi)接于，對(duì)角線與相交于，設(shè)、的外心

16、分別為、求證：、三直線共點(diǎn)證明：作反演變換，則、互為反點(diǎn)，、互為反點(diǎn)，不變，直線不變，的外接圓的反形是直線由于直線與的外接圓正交，因而與正交，即有又，所以；同理，所以四邊形為平行四邊形，從而過的中點(diǎn)；同理也過的中點(diǎn)故、三線共點(diǎn)三、證明點(diǎn)共圓例3設(shè)半圓的直徑為，圓心為，一直線與半圓交于、兩點(diǎn)，且與直線交于再設(shè)與的外接圓的第二個(gè)交點(diǎn)為求證：證明： 以為反演中心作反演變換，其中，為半圓的半徑，則半圓上的每一點(diǎn)都不變，與的反形分別為直線、且設(shè)、的反點(diǎn)分別為、，則為直線與的交點(diǎn)，在直徑上，直線的反形為的外接圓，直線的反形為的外接圓而是外接圓的直徑于是問題轉(zhuǎn)化為證明 因?yàn)?，是的中點(diǎn)，所以過、三點(diǎn)的圓是的九

17、點(diǎn)圓，而在九點(diǎn)圓上，又在邊上（不同于點(diǎn)），故，因此四、證明一些幾何（不）等式例4設(shè)六個(gè)圓都在一定圓內(nèi)，每一個(gè)圓都與定圓外切，并且與相鄰的兩個(gè)小圓外切，若六個(gè)小圓與大圓的切點(diǎn)依次為、證明：證明：如圖以為反演中心作反演變換，則與的反形為兩條平行線，其余5個(gè)圓的反形皆是與兩條平行線中一條相切的圓；且反形中第一個(gè)圓與第五個(gè)圓均與兩平行線相切，而其余三圓均與相鄰的兩圓相切設(shè)、的反點(diǎn)分別為、，則其反形中的五個(gè)圓與兩平行線中的一條（即的反形）依次切于、；再設(shè)這五個(gè)圓的半徑依次為、，則由勾股定理可得，同理，顯然，于是但，所以故練習(xí)：1（2002土耳其數(shù)學(xué)奧林匹克）兩圓外切于點(diǎn)，且內(nèi)切于另一于點(diǎn)、，另是小圓內(nèi)公

18、切線割的弦的中點(diǎn)，證明：當(dāng)、不共線時(shí)，是的內(nèi)切圓圓心2（第30屆IMO預(yù)選題）雙心四邊形是指既有內(nèi)切圓又有外接圓的四邊形證明雙心四邊形的兩個(gè)圓心與對(duì)角線的交點(diǎn)共線3（1997全國高中數(shù)學(xué)聯(lián)賽）已知兩個(gè)半徑不等的圓與圓相交于、兩點(diǎn)，圓與圓分別于圓內(nèi)切于、求證：的充分必要條件是、三點(diǎn)共線模擬試題哈師大附中 趙巖一、選擇題（每小題6分，共36分）1若集合是整數(shù)，且整除，則為（A）空集（B）單元集（C）二元集（D）無窮集2設(shè)集合，映射使對(duì)任意的，都有是奇數(shù)，則這樣的映射的個(gè)數(shù)是（A）45（B）27（C）15（D）11ABCDD1C1B1A13如圖，已知正方體，過頂點(diǎn)在空間作直線，使與直線和所成的角都等

19、于60°這樣的直線可以做（A）4條（B）3條 （C）2條 （D）1條4若方程在上有兩個(gè)不同的實(shí)數(shù)解，則參數(shù)的取值范圍是（A）0a1（B）3a1（C）a1（D）0a15，是的三元子集，滿足：中的所有元素可以組成等差數(shù)列那么，這樣的三元子集的個(gè)數(shù)是（A）（B）（C）（D）6在正整數(shù)數(shù)列中，由1開始依次按如下規(guī)則將某些數(shù)染成紅色先染1，再染2個(gè)偶數(shù)2、4；再染4后面最鄰近的3個(gè)連續(xù)奇數(shù)5、7、9；再染9后面最鄰近的4個(gè)連續(xù)偶數(shù)10、12、14、16；再染此后最鄰近的5個(gè)連續(xù)奇數(shù)17、19、21、23、25按此規(guī)則一直染下去，得到一紅色子數(shù)列1，2，4，5，7，9，12，14，16，17，則

20、在這個(gè)紅色子數(shù)列中，由1開始的第2003個(gè)數(shù)是（A）3844（B）3943（C）3945（D）4006二、填空題（每小題9分，共54分）7在四面體P-ABC中，PA=PB=a，PC=AB=BC=CA=b，且ab，則的取值范圍為 8已知，則的值是_ 9關(guān)于x的不等式的解集是一些區(qū)間的并集，且這些區(qū)間的長度的和小于4，則實(shí)數(shù)的取值范圍是 10設(shè)點(diǎn)B、C分別在第四、第一象限，且點(diǎn)B、C都在拋物線上，O為坐標(biāo)原點(diǎn)，為直線OC的斜率，則的值為 11已知函數(shù)，若的定義域?yàn)闀r(shí)，值域?yàn)?，則應(yīng)滿足的條件是_12數(shù)的末四位數(shù)字是_三、解答題13（20分）已知，（1）求的最大值與最小值；（2）求所有實(shí)數(shù)，使得對(duì)任意

21、三個(gè)實(shí)數(shù)，存在一個(gè)三角形具有邊長ABOPQxyF1F214（20分）如圖，A、B為橢圓 和雙曲線的公共頂點(diǎn).P、Q分別 為雙曲線和橢圓上不同于A、B的動(dòng)點(diǎn)，且滿足.設(shè)直線AP、BP、AQ、BQ的斜率分別是，.（1）求證：；（2）設(shè)分別為橢圓和雙曲線的右焦點(diǎn)；若，求的值15（20分）已知數(shù)列，滿足：，求證：數(shù)列中，任何相鄰兩項(xiàng)之積減等于某個(gè)完全平方數(shù)的倍 加試題1的內(nèi)心為，三角形內(nèi)一點(diǎn)滿足，求證：，而且等號(hào)當(dāng)且僅當(dāng)時(shí)成立2設(shè)，且，求證：3某國有若干個(gè)城市和個(gè)不同的航空公司任意個(gè)城市之間，或者有條屬于某個(gè)航空公司的雙向的直飛航線連接，或者沒有航線連接已知任意條同一公司的航線都有公共的端點(diǎn)證明：可以將所有的城市分為個(gè)組，使得任意個(gè)屬于同一組的城市之間都沒有航線相連模擬試題答案第一試一、選擇題：題號(hào)123456答案CABABB二、填空題：7； 8； 91,3； 10； 11； 12三、解答