五年級奧數(shù)春季實驗班第講組合數(shù)學(xué)染色及覆蓋

精選文檔精選文檔PAGE精選文檔第二講組合數(shù)學(xué)之染色與覆蓋

例1．有一次車展共36個展室，以以以下圖，每個展室與相鄰的展室都有門相通，進口和出口以以以下圖。觀光

者（填“能”或“不可以”）從人口進去，不重復(fù)地觀光完每個展室再從出口出來。

解：答：不可以；如圖將展室黑白相間染色，進口為白色，出口也是白色，而走遍36個展室，從白到黑，再從黑到白，共走了35步，最后應(yīng)該走到黑格，而出口依舊是白格，矛盾，所以沒法完成。例2．棋盤由以以下圖所示的9個小圓圈擺列而成，用1~9編號，在3號和9號的小圓圈中各方一枚棋子，分別代表警察和小偷。若兩個小圓圈之間有線相連，則棋子可以今后中一格走入另一格，此刻由警察先走，兩人輪番，每人每次走一步，每步可以從一格走到有線相連的臨格之中。假如在6步以內(nèi)警察走入小偷所在的格子中，就算警察抓住了小偷而立功獲勝；假如警察走了6步還沒有抓住小偷，就算他瀆職而失敗。問警察應(yīng)如何取勝。147369258解：警察先從3走到1，則小偷從9走到7（或8）；第2步，警察走到2，小偷走到6（或9）；第3步，警察走到3，小偷走到7或8；第4步，警察走到4，小偷走到9；第5步，警察6，小偷無論是走到7（或8），警察在第6步必定可以獲勝。

例3．空間六點任三點不共線，任四點不共面，成對地連接它們獲得十五條線段，用紅色或藍色染這些線段（一條線段只染一種顏色），求證：無論這么染，總存在一個同色的三角形。

解：設(shè)六點為A、B、C、D、E、F，從A點出發(fā)的五條線段AB、AC、AD、AE、AF中最稀有3條是同色

的，沒關(guān)系設(shè)AB、AC、AD為紅色，

我們再看△BCD的三邊，假如都是藍色，那么存在同為藍色的△BCD，

若△BCD中有一條邊不是藍色，而是紅色，沒關(guān)系設(shè)BC是紅色，則AB、AC、BC都是紅色，這是一個

紅色三角形。

所以總存在一個同色的三角形。

例4．以以下圖是由14個大小同樣的方格構(gòu)成的圖形，試問

方格構(gòu)成的長方形。

（“能”或“不可以”）剪裁成

7個由相鄰兩個

解：答：不可以；如圖，將圖形黑白相間染色，則出現(xiàn)8個黑格，6個白格，而相鄰的兩個方格構(gòu)成的長方形必定是一黑一白，矛盾，所以沒法裁成7個小長方形。例5．一個2×2正方形和15個4×1長方形（“能”或“不可以”）拼成8×8的大正方形請說明原由。解：答：不可以；1234123423412341341234124123412312341234234123413412341241234123如圖進行染色，

1個4×1矩形恰好遮住四種顏色的方格各一個，而1個2×2矩形方塊總不可以遮住四種顏色的方格各一

個，所以這16個矩形塊遮住的4種顏色的方格數(shù)不同樣，而圖中的四種顏色的方格數(shù)是同樣的，矛盾。

所以用15個4×1矩形塊和1個2×2矩形塊不可以完滿覆蓋8×8矩形。

例6．在6×6×6的正方體盒子中最多可以放入

子的側(cè)面平行。

解：分上下兩層，基層高度為4，則6×6×4中豎著放

上層高度為2，都只好橫著放，每層最多能放入

36+16=52。所以最多放入52個小長方體。

個1×1×4的小長方體這里每個小長方體的面都要與盒

36個小長方體；

8個小長方體，所以2×8=16，

例7．在一個6×6的方格棋盤中，將若干個1×1的小方格染成紅色，假如隨意劃掉3行3列，在剩下的小方

格中必定有一個是紅色的，那么最少要染個方格。

解：先考慮每行每列都有一個紅格，比較方便的涂法是在一條對角線上涂6格紅色的（如圖1），

隨意劃掉3行3列，可以假想劃行劃列的原則是：每次劃掉的紅格越多越好，對于圖1，劃掉3行去掉

了3個紅格，還有3個紅格在3列中，再劃掉3列就不存在紅格了，

所以必有一些行一些列要涂2個紅格，為了盡可能的少涂紅格，那么每涂一個紅色的，必定要使多出

一行的同時，也多出一列有兩個紅色的；

先考慮有3行中有2格涂紅（如圖2），明顯，同時必定有3個列中也有2格紅色的，這時，我們可以

劃掉有2格紅色的3行，還剩下3行，每行上只有一個涂紅，每列上也只有一格涂紅，那么再帶紅格的3

列就沒有紅格了；

為了使最少余下一個紅格，只要再涂一個紅格，此紅格要使圖中再增加一行一列有兩個紅格的，如圖

3；

所以，結(jié)論是：最少需要涂紅

10個方格．

例8．將15×15的正方形方格表的每個格涂上色、色或色。明最少可以找到兩行，兩行中某一種色的格數(shù)同樣。

解：假如不存在兩行，兩行中某一種色的格數(shù)同樣.

色在不同樣的行中有不同樣的格數(shù)，所以色格數(shù)最少0+1+2+??+14＝105個，

同色或色的格數(shù)都≥105個，共最少315個格子。但是一共只有15×15=225個格子

所以是不可以能的.

所以最少可以找到兩行，兩行中某一種色的格數(shù)同樣.

隨堂測

試

1．下是小學(xué)素教育成就展會的展室，每兩個相的展室之都有相通，有一個人打算從挨次而入，不重復(fù)地看各室展今后，仍回到A室，他的目的能否達到，什么

A室開始

A

A

解：答：不可以；

將中方格黑白相染色，有5個黑格，4個白格，依據(jù)個人的走法，每次從黑格走到白格也許從白格走到黑格，奇數(shù)步走入白格，偶數(shù)步走入黑格，

他從A室出，走遍各室回到A室，一共走九步，最后走到白格，與A室黑格矛盾，所以他的目的不可以達到。

2．下是半中國象棋棋，棋上放有一只，眾所周知，是走“日”字的。：只或“不可以”）不重復(fù)地走遍棋上的每一個點，此后回到出點。

（“能”

○馬○馬

解：答：不可以；

將中的點相染色，如在在色點上，按的走法，它下一步走到的點必定是色的點，同從色點出必定走到色的點。所以它走奇數(shù)步走到色點，偶數(shù)步走到色點。

在一共有5×9=45個點，從色點出不重復(fù)地走遍各點，回到本來的地點，一共走49步，到達色點，而本來是從色點出的，矛盾。所以沒法完成上述任。

3．將段AA挨次用分點A，A，??，An?1分成n段小段，將端點A和A涂成色，中的分點涂0n120n上色或色，那么在n段小段中，端點異色的小段的條數(shù)（）A．偶數(shù)B．奇數(shù)C．不用然解：答：A，有偶數(shù)條端點異色的小段；假如n+1個點都涂成色，那么中端點異色的小段的條數(shù)0條，0是偶數(shù)，將中的n?1個點中的某一個點成色，那么中端點異色的小段的條數(shù)2條，2是偶數(shù)，再將剩下的點中某一個點成色，假如它與前面的點相，那么中端點異色的小段的條數(shù)不，假如它與前面的點不相，那么中端點異色的小段的條數(shù)增加2條，條數(shù)依舊是偶數(shù)，增加點的個數(shù)，假如新增加的點恰好將本來兩個點之的點成點今后，使得原來斷開的兩部分點成一串，那么端點異色的小段的條數(shù)減少2條，條數(shù)是偶數(shù)。依據(jù)個律增加點，直到全部的點都成色點，條數(shù)是偶數(shù)。

4．下是有40個1的小正方形成的形，從它上邊最多能剪出個和分2和1的

方形。

解：答：19個；

如將棋黑白染色，按在的染色方法獲得21個黑色的方格和19個白色的方格，

而美國和分2×1的方形，需要占一個黑格和一個白格，所以最多剪出19個方形。

5．用若干個2×2和3×3的小正方形（“能”或“不可以”）拼成一個11×11的大正方形明原由。解：答：不可以；

如將11×11的大正方形按條形黑白相染色，在黑色比白色的小方格多11個。于2×2的小正方形，無如何擱置，黑格和白格都一多，而于3×3的小正方形，可能是6黑3白，也可能是3黑6白，它的差都是3個，也就是黑白小格的差必定是3的倍數(shù)。而于可能用到的3×3的小正方形的個數(shù)，無是多少個，黑白小格的差都不會是11.矛盾。所以沒法覆蓋。

6．如，把正方體的6個表面均剖分成9個相等的正方形，用、黃、

要求有公共的正方形所染的色不同樣。那么染成色的正方形的個數(shù)最多是

3種色去染些小正方形，

個。

解：答案：22塊；

先涂前面的一塊，最多可以有5個小正方形涂成紅色，即四角和中心。

這時與它相鄰的面（如右邊）最多有4塊可以涂成紅色，假如后邊與左面與它們對稱染色，

則這時已經(jīng)有(5+4)×2=18個紅格，此時上下邊只好各有2個面染成紅色，

7．在1000×1000的方格表中隨意采用n個方格染成紅色，都存在3個紅色方格，它們的中心構(gòu)成一個直角

三角形的極點。N的最小值是。

解：答案：1999；

假如我們在正方形ABCD的相鄰兩邊，AB、BC上取除了它們重合的小方分外的999×2=1998個方格，

把它們涂成紅色，那么它們的中心都不可以構(gòu)成一個直角三角形的極點。

下邊證明任取1999個方格必定可以成立。

先看行，在1000行中，最稀有一些行中最稀有兩個格子是紅色的，

那么由于含有0或1個紅點的行最多999個，所以其余行含有紅點必定大于等于1999?999=1000，

假如是大于1000，那么依據(jù)抽屜原理，必定有兩個這樣紅點在一列，那么就會出現(xiàn)紅色三角形；

假如是等于1000而沒有這樣的2個紅點在一列，說明有999行只含有1個紅點，而剩下的一行全部是紅

點，那也必定已經(jīng)出現(xiàn)直角三角形了，所以n的最小值為1999.

8．大廳中齊集了

100個客人，他們中每人最少認識

67個人，證明在這些客人中必定可以找到

4人，他們

之中任何兩人都相互認識。

證明：在此中先確立A，A最少認識67人，有不多于32人（99?67=32）不認識；在這67人中選定B，A與B認識，B除了認識A以外，假如他還認識其余的

32