組合數(shù)學(xué)之染色與覆蓋例1．有一次車展共36個(gè)展室，如下圖，每個(gè)展室與相鄰的展室都有門相通，入口和出口如圖所示。參觀者（填“能”或“不能”）從人口進(jìn)去，不重復(fù)地參觀完每個(gè)展室再從出口出來。解：答：不能；如圖將展室黑白相間染色，入口為白色，出口也是白色，而走遍36個(gè)展室，從白到黑，再從黑到白，共走了35步，最后應(yīng)該走到黑格，而出口仍然是白格，矛盾，所以無法完成。例2．棋盤由下圖所示的9個(gè)小圓圈排列而成，用1~9編號(hào)，在3號(hào)和9號(hào)的小圓圈中各方一枚棋子，分別代表警察和小偷。若兩個(gè)小圓圈之間有線相連，則棋子可以從其中一格走入另一格，現(xiàn)在由警察先走，兩人輪流，每人每次走一步，每步可以從一格走到有線相連的臨格之中。如果在6步之內(nèi)警察走入小偷所在的格子中，就算警察抓住了小偷而立功獲勝；如果警察走了6步還沒有抓住小偷，就算他失職而失敗。問警察應(yīng)如何取勝。解：警察先從3走到1，則小偷從9走到7（或8）；第2步，警察走到2，小偷走到6（或9）；第3步，警察走到3，小偷走到7或8；第4步，警察走到4，小偷走到9；第5步，警察6，小偷無論是走到7（或8），警察在第6步一定可以獲勝。例3．空間六點(diǎn)任三點(diǎn)不共線，任四點(diǎn)不共面，成對(duì)地連接它們得到十五條線段，用紅色或藍(lán)色染這些線段（一條線段只染一種顏色），求證：無論這么染，總存在一個(gè)同色的三角形。解：設(shè)六點(diǎn)為A、B、C、D、E、F，從A點(diǎn)出發(fā)的五條線段AB、AC、AD、AE、AF中至少有3條是同色的，不妨設(shè)AB、AC、AD為紅色，我們?cè)倏础鰾CD的三邊，如果都是藍(lán)色，那么存在同為藍(lán)色的△BCD，若△BCD中有一條邊不是藍(lán)色，而是紅色，不妨設(shè)BC是紅色，則AB、AC、BC都是紅色，這是一個(gè)紅色三角形。所以總存在一個(gè)同色的三角形。例4．下圖是由14個(gè)大小相同的方格組成的圖形，試問（“能”或“不能”）剪裁成7個(gè)由相鄰兩個(gè)方格組成的長方形。解：答：不能；如圖，將圖形黑白相間染色，則出現(xiàn)8個(gè)黑格，6個(gè)白格，而相鄰的兩個(gè)方格組成的長方形一定是一黑一白，矛盾，所以無法裁成7個(gè)小長方形。例5．一個(gè)2×2正方形和15個(gè)4×1長方形（“能”或“不能”）拼成8×8的大正方形？請(qǐng)說明理由。解：答：不能；1234123423412341341234124123412312341234234123413412341241234123如圖進(jìn)行染色，1個(gè)4×1矩形恰好蓋住四種顏色的方格各一個(gè)，而1個(gè)2×2矩形方塊總不能蓋住四種顏色的方格各一個(gè)，因此這16個(gè)矩形塊蓋住的4種顏色的方格數(shù)不同，而圖中的四種顏色的方格數(shù)是相同的，矛盾。所以用15個(gè)4×1矩形塊和1個(gè)2×2矩形塊不能完全覆蓋8×8矩形。例6．在6×6×6的正方體盒子中最多可以放入個(gè)1×1×4的小長方體？這里每個(gè)小長方體的面都要與盒子的側(cè)面平行。解：分上下兩層，下層高度為4，則6×6×4中豎著放36個(gè)小長方體；上層高度為2，都只能橫著放，每層最多能放入8個(gè)小長方體，所以2×8=16，36+16=52。所以最多放入52個(gè)小長方體。例7．在一個(gè)6×6的方格棋盤中，將若干個(gè)1×1的小方格染成紅色，如果隨意劃掉3行3列，在剩下的小方格中必定有一個(gè)是紅色的，那么最少要染個(gè)方格。解：先考慮每行每列都有一個(gè)紅格，比較方便的涂法是在一條對(duì)角線上涂6格紅色的（如圖1），任意劃掉3行3列，可以設(shè)想劃行劃列的原則是：每次劃掉的紅格越多越好，對(duì)于圖1，劃掉3行去掉了3個(gè)紅格，還有3個(gè)紅格在3列中，再劃掉3列就不存在紅格了，所以必有一些行一些列要涂2個(gè)紅格，為了盡可能的少涂紅格，那么每涂一個(gè)紅色的，一定要使多出一行的同時(shí)，也多出一列有兩個(gè)紅色的；先考慮有3行中有2格涂紅（如圖2），顯然，同時(shí)必然有3個(gè)列中也有2格紅色的，這時(shí)，我們可以劃掉有2格紅色的3行，還剩下3行，每行上只有一個(gè)涂紅，每列上也只有一格涂紅，那么再帶紅格的3列就沒有紅格了；

為了使至少余下一個(gè)紅格，只要再涂一個(gè)紅格，此紅格要使圖中再增加一行一列有兩個(gè)紅格的，如圖3；

所以，結(jié)論是：至少需要涂紅10個(gè)方格．例8．將15×15的正方形方格表的每個(gè)格涂上紅色、藍(lán)色或綠色。證明至少可以找到兩行，這兩行中某一種顏色的格數(shù)相同。解：假如不存在兩行，這兩行中某一種顏色的格數(shù)相同.則紅色在不同的行中應(yīng)該有不同的格數(shù)，所以紅色格數(shù)至少0+1+2+……+14＝105個(gè)，同樣藍(lán)色或綠色的格數(shù)都≥105個(gè)，共計(jì)至少315個(gè)格子。但是一共只有15×15=225個(gè)格子所以這是不可能的.所以至少可以找到兩行，這兩行中某一種顏色的格數(shù)相同.隨堂測試1．下圖是小學(xué)素質(zhì)教育成果展覽會(huì)的展室，每兩個(gè)相鄰的展室之間都有門相通，有一個(gè)人打算從A室開始依次而入，不重復(fù)地看過各室展覽之后，仍回到A室，問他的目的能否達(dá)到，為什么？解：答：不能；將圖中方格黑白相間染色，有5個(gè)黑格，4個(gè)白格，按照這個(gè)人的走法，每次從黑格走到白格或者從白格走到黑格，奇數(shù)步走入白格，偶數(shù)步走入黑格，他從A室出發(fā)，走遍各室回到A室，一共走九步，應(yīng)該最后走到白格，與A室為黑格矛盾，所以他的目的不能達(dá)到。2．下圖是半張中國象棋棋盤，棋盤上放有一只馬，眾所周知，馬是走“日”字的。請(qǐng)問：這只馬（“能”或“不能”）不重復(fù)地走遍棋盤上的每一個(gè)點(diǎn)，然后回到出發(fā)點(diǎn)。解：答：不能；將圖中的點(diǎn)紅藍(lán)相間染色，如圖現(xiàn)在馬在藍(lán)色點(diǎn)上，按馬的走法，它下一步走到的點(diǎn)一定是紅色的點(diǎn)，同樣從紅色點(diǎn)出發(fā)一定走到藍(lán)色的點(diǎn)。所以它走奇數(shù)步走到紅色點(diǎn)，偶數(shù)步走到藍(lán)色點(diǎn)?，F(xiàn)在一共有5×9=45個(gè)點(diǎn)，該馬從藍(lán)色點(diǎn)出發(fā)不重復(fù)地走遍各點(diǎn)，回到原來的位置，一共走49步，應(yīng)該到達(dá)紅色點(diǎn)，而原來是從藍(lán)色點(diǎn)出發(fā)的，矛盾。所以無法完成上述任務(wù)。3．將線段A0An依次用分點(diǎn)A1，A2，……，An?1分成n段小線段，將端點(diǎn)A0和An涂成藍(lán)色，中間的分點(diǎn)涂上紅色或藍(lán)色，那么在這n段小線段中，端點(diǎn)異色的小線段的條數(shù)為（）A．偶數(shù)B．奇數(shù)C．不一定解：答：選A，有偶數(shù)條端點(diǎn)異色的小線段；如果這n+1個(gè)點(diǎn)都涂成藍(lán)色，那么圖中端點(diǎn)異色的小線段的條數(shù)為0條，0是偶數(shù)，將中間的n?1個(gè)點(diǎn)中的某一個(gè)點(diǎn)變成紅色，那么圖中端點(diǎn)異色的小線段的條數(shù)為2條，2是偶數(shù)，再將剩下的點(diǎn)中某一個(gè)點(diǎn)變成紅色，如果它與前面的紅點(diǎn)相鄰，那么圖中端點(diǎn)異色的小線段的條數(shù)不變，如果它與前面的紅點(diǎn)不相鄰，那么圖中端點(diǎn)異色的小線段的條數(shù)增加2條，總條數(shù)仍然是偶數(shù)，繼續(xù)增加紅點(diǎn)的個(gè)數(shù)，如果新添加的紅點(diǎn)恰好將原來兩個(gè)紅點(diǎn)之間的藍(lán)點(diǎn)變?yōu)樽兂杉t點(diǎn)之后，使得原來斷開的兩部分紅點(diǎn)連成一串，那么端點(diǎn)異色的小線段的條數(shù)減少2條，總條數(shù)還是偶數(shù)。按照這個(gè)規(guī)律繼續(xù)添加紅點(diǎn)，直到所有的點(diǎn)都成為紅色點(diǎn)，總條數(shù)還是偶數(shù)。4．下圖是有40個(gè)邊長為1的小正方形組成的圖形，從它上面最多能剪出個(gè)長和寬分別為2和1的長方形。解：答：19個(gè)；如圖將棋盤黑白染色，按現(xiàn)在的染色方法得到21個(gè)黑色的方格和19個(gè)白色的方格，而美國長和寬分別為2×1的長方形，需要占一個(gè)黑格和一個(gè)白格，所以最多剪出19個(gè)長方形。5．用若干個(gè)2×2和3×3的小正方形（“能”或“不能”）拼成一個(gè)11×11的大正方形？請(qǐng)說明理由。解：答：不能；如圖將11×11的大正方形按條形黑白相間染色，現(xiàn)在黑色比白色的小方格多11個(gè)。對(duì)于2×2的小正方形，無論如何放置，黑格和白格都一樣多，而對(duì)于3×3的小正方形，可能是6黑3白，也可能是3黑6白，它們的差都是3個(gè)，也就是黑白小格的差一定是3的倍數(shù)。而對(duì)于可能用到的3×3的小正方形的個(gè)數(shù)，無論是多少個(gè)，黑白小格的差都不會(huì)是11.矛盾。所以無法覆蓋。6．如圖，把正方體的6個(gè)表面均剖分成9個(gè)相等的正方形，現(xiàn)用紅、黃、藍(lán)3種顏色去染這些小正方形，要求有公共邊的正方形所染的顏色不同。那么染成紅色的正方形的個(gè)數(shù)最多是個(gè)。解：答案：22塊；先涂前面的一塊，最多可以有5個(gè)小正方形涂成紅色，即四角和中心。這時(shí)與它相鄰的面（如右面）最多有4塊可以涂成紅色，如果后面與左面與它們對(duì)稱染色，則這時(shí)已經(jīng)有(5+4)×2=18個(gè)紅格，此時(shí)上下面只能各有2個(gè)面染成紅色，7．在1000×1000的方格表中任意選取n個(gè)方格染成紅色，都存在3個(gè)紅色方格，它們的中心構(gòu)成一個(gè)直角三角形的頂點(diǎn)。N的最小值是。解：答案：1999；如果我們?cè)谡叫蜛BCD的相鄰兩邊，AB、BC上取除了它們重合的小方格外的999×2=1998個(gè)方格，把它們涂成紅色，那么它們的中心都不能構(gòu)成一個(gè)直角三角形的頂點(diǎn)。下面證明任取1999個(gè)方格一定能夠成立。先看行，在1000行中，至少有一些行中至少有兩個(gè)格子是紅色的， 那么因?yàn)楹?或1個(gè)紅點(diǎn)的行最多999個(gè)，所以其他行含有紅點(diǎn)肯定大于等于1999?999=1000，如果是大于1000，那么根據(jù)抽屜原理，肯定有兩個(gè)這樣紅點(diǎn)在一列，那么就會(huì)出現(xiàn)紅色三角形；如果是等于1000而沒有這樣的2個(gè)紅點(diǎn)在一列，說明有999行只含有1個(gè)紅點(diǎn)，而剩下的一行全是紅點(diǎn)，那也肯定已經(jīng)出現(xiàn)直角三角形了，所以n的最小值為1999.8．大廳中聚集了100個(gè)客人，他們中每人至少認(rèn)識(shí)67個(gè)人，證明在這些客人中一定可以找到4人，他們之中任何兩人都彼此相識(shí)。證明：在其中先確定A，A至少認(rèn)識(shí)67人，有不多于32人（99?67=32）不認(rèn)識(shí)；在這67人中選定B，A與B認(rèn)