培訓體系競賽培訓專題染色問題與染色方法

1、培訓體系）競賽培訓 專題染色問題與染色 方法競賽培訓專題 2- 染色問題和染色方法1 小方格染色問題最簡單的染色問題是從壹種民間游戲中發(fā)展起來的方格盤上的染色問題.解決這類問題的方法后來又發(fā)展成為解決方格盤鋪蓋問題的重要技巧 .例1 如圖 29-1（a）,3 行7列小方格每壹個染上紅色或藍色 .試證:存于壹個矩形 它的四個角上的小方格顏色相同 .證明由抽屜原則 ,第 1 行的 7 個小方格至少有 4 個不同色 ,不妨設為紅色 （ 帶陰 影）且于 1、2、3、4 列（如圖 29-1 （b） .于第 1、2、3、4 列（以下不必再考慮第 5，6，7 列）中，如第 2 行或第 3 行出現(xiàn)倆個紅色小方

2、格， 則這個問題已經(jīng)得證；如第 2 行和第 3 行每行最多 只有壹個紅色小方格（如圖 29-1 （ c），那么于這倆行中必出現(xiàn)四角同為 藍色的矩形，問題也得到證明 .說明：（ 1 ）于上面證明過程中除了運用抽屜原則外，仍要用到壹種思考問 題的有效方法，就是逐步縮小所要討論的對象的范圍，把復雜問題逐步化為 簡單問題進行處理的方法2 ）此例的行和列均不能再減少了 .顯然只有倆行的方格盤染倆色后是不壹定存于頂點同 色的矩形的 .下面我們舉出壹個 3 行 6 列染倆 色不存于頂點同色矩形的例子如圖 29-2. 這說 明3 行7 列是染倆色存于頂點同色的矩形的最 小方格盤了 .至今 ,染 k 色而存于頂

3、點同色的矩 形的最小方格盤是什么仍不得而知 .例2（第2屆全國部分省市初中數(shù)學通訊賽題）證明:用 15塊大小是 4×1的矩形瓷磚和 1 塊大小是 2 ×2的矩形瓷磚，不能恰好鋪蓋 8 ×8矩形的地面 .分析將 8 ×8矩形地面的壹半染上壹種顏色，另壹半染上另壹種顏色，再用4 ×1和 2 ×2的矩形瓷磚去蓋，如果蓋住的倆種顏色的小矩形不是壹樣多， 則說明于給定條件不完滿鋪蓋不可能 .證明如圖 29-3 ，用間隔為倆格且和副對角線平行的斜格同色的染色方式， 以 黑白倆種顏色將整個地面的方格染色 .顯然，地面上黑、白格各有 32 個 .每塊

4、 4 ×1的矩形磚不論是橫放仍是豎蓋， 且不論蓋于何處， 總是占據(jù)地面上 的倆個白格、倆個黑格，故 15 塊 4 ×1的矩形磚鋪蓋后仍剩倆個黑格和倆個白格 .但由于和副對角線平行的斜格總是同色， 而和主對角線平行的相鄰格總是異色， 所以，不論怎樣放置，壹塊 2 ×2的矩形磚，總是蓋住三黑壹白或壹 黑三白 .這說明剩下的壹塊 2 ×2矩形磚無論如何蓋不住剩下的二黑二白的地 面 .從而問題得證 .例 3（ 1986 年北京初二數(shù)學競賽題）如圖29-4 （ 1）是 4 個 1×1的正方形組成的“ L ”形，用若干個這種L”形硬紙片無重迭拼成m壹

5、15;個n（長為m 個單位，寬為 n 個單位）的矩形如圖29-4 （2） .試證明 mn 必是 8 的倍數(shù).證明 m×n矩形由“ L”形拼成，是m×4 n的倍數(shù)， mn、中必有壹個是偶數(shù)， 不妨設為 m. 把 m×n 矩形中的 m 列按壹列黑、 壹列白間隔染色 （如圖 29-4 （ 2），則不論“L”形于這矩形中的放置位置如何（“L”形的放置，共有 8 種可能），“L ”形或占3有白壹黑四個單位正方形（第壹種），或占有 3 黑壹白四個單位正方形（第二種） .設第壹種“L”形共有p 個，第二種“L”形q共個，則 m×n 矩形中的白格單位正方形數(shù)為 3p+q

6、 ，而它的黑格單位正方形數(shù)為 p+3q.m 為偶數(shù)，m×矩n形中黑、白條數(shù)相同，黑、白單位正方形總數(shù)也必相等故有 3p+q=p+3q ，從而 p=q. 所以“ L”形的總數(shù)為 2p 個，即“ L”形總數(shù)為偶數(shù)，所以m×n壹定是 8 的倍 數(shù).2 線段染色和點染色下面介紹倆類重要的染色問題 .（1） 線段染色 .較常見的壹類染色問題是發(fā)樣子組合數(shù)學中圖論知識的所謂 “邊染色”（或稱“線段染色”），主要借助抽屜原則求解 .例 4（ 1947 年匈牙利數(shù)學奧林匹克試題）世界上任何六個人中，壹定有 3 個人或者互相認識或者互相均不認識 .我們不直接證明這個命題，而來見和之等價的下述

7、命題例 5（ 1953 年美國普特南數(shù)學競賽題） 空間六點， 任三點不共線， 任四點不 共面，成對地連接它們得十五條線段，用紅色或藍色染這些線段（壹條線段 只染壹種顏色） .求證 :無論怎樣染 ,總存于同色三角形 .證明設 A、B、C、D、E、F是所給六點 .考慮以 A 為端點的線段 AB、AC、AD 、AE、 AF，由抽屜原則這五條線段中至少有三條顏色相同，不妨設就是 AB、AC、AD ，且它們均染成紅色 .再來見 BC的D三邊，如其中有壹條邊例如 BC 是紅色的，則同色三角形已出現(xiàn)（紅色ABC）三；邊如均不是BCD紅色的，則它就是藍色的三角形，同色三角形也現(xiàn)了.總之 ,不論于哪種情況下 ,

8、均存于同色三角形 .如果將例 4 中的六個人見成例 5 中六點 ,倆人認識的連紅線 ,不認識的連藍線 , 則例 4 就變成了例 5. 例 5 的證明實際上用染色方法給出了例4 的證明 .例6（第6屆國際數(shù)學奧林匹克試題 ）有17位科學家 ,其中每壹個人和其他所 有人的人通信 ,他們的通信中只討論三個題目 .求證 :至少有三個科學家相互之 間討論同壹個題目 .證明用平面上無三點共線的 17 個點 A1 ,A2, ，A17 分別表示 17 位科學家 .設 他們討論的題目為 x,y,z,倆位科學家討論 x連紅線,討論y連藍線,討論 z連黃 線 .于是只須證明以這 17 個點為頂點的三角形中有壹同色三

9、角形 .考慮以 A 1為端點的線段 A1A2,A1A3, ，A1A17 ，由抽屜原則這 16 條線段中 至少有 6條同色，不妨設 A1A2，A1A3，A1A7為紅色 .現(xiàn)考查連結六點 A2，A3，A7的 15 條線段，如其中至少有壹條紅色線段，則同色（紅色） 三角形已出現(xiàn)；如沒有紅色線段，則這 15 條線段只有藍色和黃色，由例 5 知壹定存于以這 15 條線段中某三條為邊的同色三角形（藍色或黃色）.問題得證.上述三例同屬圖論中的接姆賽問題 .于圖論中 ,將 n 點中每倆點均用線段相連 所得的圖形叫做 n 點完全圖 ,記作 kn.這些點叫做“頂點”，這些線段叫做“邊” . 當下我們分別用圖論的語

10、言來敘述例 5 、例 6.定理 1 若于 k6 中，任染紅、藍倆色，則必有壹只同色三角形.定理 2 于 k17 中 ,任染紅、藍、黃三角，則必有壹只同色三角形.（ 2）點染色 .先見離散的有限個點的情況 .例 7（首屆全國中學生數(shù)學冬令營試題）能否把1 ，1，2，2，3，3，1986 ，1986 這些數(shù)排成壹行，使得倆個 1 之間夾著壹個數(shù)，倆個 2 之間夾 著倆個數(shù)， ，倆個 1986 、之間夾著壹千九百八十六個數(shù)？請證明你的結論證明將 1986 ×2個位置按奇數(shù)位著白色， 偶數(shù)位著黑色染色， 于是黑白點各 有 1986 個 .現(xiàn)令壹個偶數(shù)占據(jù)壹個黑點和壹個白色，同壹個奇數(shù)要么均占

11、黑點，要么均占白點 .于是 993 個偶數(shù)，占據(jù)白點 A 1=993 個，黑色 B1=993 個.993 個奇數(shù)，占據(jù)白點 A2=2a 個，黑點 B2=2b 個，其中 a+b=993.因此，共占白色 A=A 1+A 2=993+2a 個.黑點 B=B 1+B 2=993+2b 個，由于 a+b=993 （非偶數(shù)！）a b ，從A而得B. 這和黑、白點各有 1986個矛盾 .故這種排法不可能“點”能夠是有限個，也能夠是無限個，這時染色問題總是和相應的幾何問 題聯(lián)系于壹起的 .例 8 對平面上壹個點，任意染上紅、藍、黑三種顏色中的 壹種 .證明 :平面內(nèi)存于端點同色的單位線段 .證明作出壹個如圖

12、29-7 的幾何圖形是可能的 ,其中 ABD、 CBD、 AEF 、均是GE邊F長為 1 的等邊三角 形， CG=1. 不妨設 A 點是紅色，如果 B、E、D、F 中有紅 色，問題顯然得證 .當B、 E、 D、 F均為藍點或黃點時，又如果 B和D或 E和 F 同色，問題也得證 .現(xiàn)設 B 和 D 異色 E 和 F 異色 ,于這種情況下 , 如果 C 或G 為黃色或藍點 ,則 CB、CD、GE、GF 中有倆條是端點同色的單位線段，問題也得證 .不然的話 ,C、G 均為紅點，這時 CG 是端點同色的單位線段 .證畢 .仍有壹類較難的對區(qū)域染色的問題，就不作介紹了練習1 6 ×6的方格盤，

13、能否用壹塊大小為 3 格，形如的彎角板和 11 塊大小為 3 ×1的矩形板，不重迭不遺漏地來鋪滿整個盤面 .2 （第 49 屆蘇聯(lián)基輔數(shù)學競賽題）于倆張 1982 × 1983的方格紙涂上紅、 黑倆種顏色， 使得每壹行及每壹列均有偶數(shù)個方格是黑色的.如果將這倆張紙重迭時，有壹個黑格和壹個紅格重合，證明至少仍有三個方格和不同顏色的 方格重合 .3 有九名數(shù)學家，每人至多會講三種語言，每三名中至少有 2 名能通話， 那么其中必有 3 名能用同壹種語言通話 .4 如果把上題中的條件 9 名改為 8 名數(shù)學家，那么，這個結論仍成立嗎？ 為什么？5設 n=6 （ r-2 ）+3 （

14、r 3），求證：如果有 n 名科學家，每人至多會講 3 種語言，每 3 名中至少有 2 名能通話，那么其中必有 r 名能用同壹種語言通 話.6 （1966 年波蘭數(shù)學競賽題） 大廳中會聚了 100 個客人， 他們中每人至少 認識 67 人，證明于這些客人中壹定能夠找到 4 人，他們之中任何倆人均彼 此相識 .7 （首屆全國數(shù)學冬令營試題）用任意方式給平面上的每壹個點染上黑色 或白色 .求證：壹定存于壹個邊長為 1 或的正三角形，它三個頂點是同色的練習答案將、行染紅色、行染黃色、行染藍色，然后就彎角板 蓋住板面的不同情況分類討論設第壹張紙上的黑格和第二張紙上的紅格重合 如果于第壹張紙上所于的列中

15、，其余的黑格（奇數(shù)個）均和第二張紙的黑格重合，那么由第 二張紙上這壹列的黑格個數(shù)為偶數(shù)，知必有壹黑格和第壹張紙上的紅格重 合，即于這壹列，第壹張紙上有壹方格和第二張紙上不同顏色的方格 重合同理于、所于行上各有壹個方格、，第二張紙上和它們重合 的方格、的顏色分別和、不同把名數(shù)學家用點 ， ， 表示倆人能通話，就用線連結，且涂某種顏色，以表示不同語種。倆人不通話，就不連線（）果任倆點均有連線且涂有顏色，那么必有壹點如，以其為壹端點的條線段中至少有倆條同色，比如、可見 ， ，之間可用同壹語言通話如情況不發(fā)生，則至少有倆點不連線，比如 、 由題設任三點必有壹條連線知，其余七點必和或 有連線這時七條線中，必有四條是從某壹點如引出的而這四條線中又必有二條同色，則問題得證結論不成立， 如圖所示 （圖中每條線旁均有壹個數(shù)字， 以表示不同語種） 類似于第題證明用點 、 、 表示客人，紅、藍的連線分別表示倆人相識 或不相識，因為由壹個頂點引出的藍色的線段最多有條，所以其中至少 有三點之間連紅線這三個點（設為 、