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

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

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

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

解：答：不可以；如圖將展室黑白相間染色，進(jìn)口為白色，出口也是白色，而走遍36個(gè)展室，從白到黑，再從黑到白，共走了35步，最后應(yīng)該走到黑格，而出口依舊是白格，矛盾，所以沒法完成。例2．棋盤由以以下圖所示的9個(gè)小圓圈擺列而成，用1~9編號，在3號和9號的小圓圈中各方一枚棋子，分別代表警察和小偷。若兩個(gè)小圓圈之間有線相連，則棋子可以今后中一格走入另一格，此刻由警察先走，兩人輪番，每人每次走一步，每步可以從一格走到有線相連的臨格之中。假如在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．空間六點(diǎn)任三點(diǎn)不共線，任四點(diǎn)不共面，成對地連接它們獲得十五條線段，用紅色或藍(lán)色染這些線段（一條線段只染一種顏色），求證：無論這么染，總存在一個(gè)同色的三角形。

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

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

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

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

紅色三角形。

所以總存在一個(gè)同色的三角形。

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

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

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

7個(gè)由相鄰兩個(gè)

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

子的側(cè)面平行。

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

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

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

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

36個(gè)小長方體；

8個(gè)小長方體，所以2×8=16，

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

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

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

隨意劃掉3行3列，可以假想劃行劃列的原則是：每次劃掉的紅格越多越好，對于圖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è)格涂上色、色或色。明最少可以找到兩行，兩行中某一種色的格數(shù)同樣。

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

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

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

所以是不可以能的.

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

隨堂測

試

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

A室開始

A

A

解：答：不可以；

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

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

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

（“能”

○馬○馬

解：答：不可以；

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

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

3．將段AA挨次用分點(diǎn)A，A，??，An?1分成n段小段，將端點(diǎn)A和A涂成色，中的分點(diǎn)涂0n120n上色或色，那么在n段小段中，端點(diǎn)異色的小段的條數(shù)（）A．偶數(shù)B．奇數(shù)C．不用然解：答：A，有偶數(shù)條端點(diǎn)異色的小段；假如n+1個(gè)點(diǎ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ù)，增加點(diǎn)的個(gè)數(shù)，假如新增加的點(diǎn)恰好將本來兩個(gè)點(diǎn)之的點(diǎn)成點(diǎn)今后，使得原來斷開的兩部分點(diǎn)成一串，那么端點(diǎn)異色的小段的條數(shù)減少2條，條數(shù)是偶數(shù)。依據(jù)個(gè)律增加點(diǎn)，直到全部的點(diǎn)都成色點(diǎn)，條數(shù)是偶數(shù)。

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

方形。

解：答：19個(gè)；

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

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

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

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

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

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

3種色去染些小正方形，

個(gè)。

解：答案：22塊；

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

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

則這時(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；

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

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

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

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

那么由于含有0或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人，他們

之中任何兩人都相互認(rèn)識(shí)。

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

32