簡單的染色問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20、在這個紅色子數(shù)列中，由1開始的第2003個數(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關于x的不等式的解集是一些區(qū)間的并集，且這些區(qū)間的長度的和小于4，則實數(shù)的取值范圍是 10設點B、C分別在第四、第一象限，且點B、C都在拋物線上，O為坐標原點，為直線OC的斜率，則的值為 11已知函數(shù)，若的定義域為時，值域為，則應滿足的條件是_12數(shù)的末四位數(shù)字是_三、解答題13（20分）已知，（1）求的最大值與最小值；（2）求所有實數(shù)，使得對任意

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