六年級奧林匹克數(shù)學講義二十 染色問題（二） 試題

1、二十、染色問題（二）1. 下圖是一套房子的平面圖,圖中的方格代表房間,每個房間都有通向任何一個鄰室的門.有人想從某個房間開始,依次不重復(fù)地走遍每一個房間,他的想法能實現(xiàn)嗎?2.展覽會有36個展室(如圖),每兩相鄰展室之間均有門相通.能不能從入口進去,不重復(fù)地參觀完全部展室后,從出口出來呢?3.圖中的16個點表示16個城市,兩個點之間的連線表示這兩個城市有公路相通.問能否找到一條不重復(fù)地走遍這16座城市的路線?hhhhhhhhhhhhhhhh4.下圖是由4個小方格組成的“l(fā)”形硬紙片,用若干個這種紙片無重疊地拼成一個4´n的長方形,試證明:n一定是偶數(shù).5.中國象棋盤上最多能放幾只馬互

2、不相“吃”(“馬”走“日”字,另不考慮“別馬腿”的情況). 6.能否用一個田字和15個4´1矩形覆蓋8´8棋盤?7.能否用1個田字和15個t字紙片,拼成一個8´8的正方形棋盤?8.在8´8棋盤上,馬能否從左下角的方格出發(fā),不重復(fù)地走遍棋盤,最后回到起點？若能請找出一條路,若不能,請說明理由.9.下面三個圖形都是從4´4的正方形分別剪去兩個1´1的小方格得到的,問可否把它們分別剪成1´2的七個小矩形? (1) (2) (3) 10.把三行七列的21個小格組成的矩形染色,每個小格染上紅、藍兩種色中的一種.求證:總可以找到4個同色

3、小方格,處于某個矩形的4個角上(如圖)123紅紅紅紅11.17個科學家互相通信,在他們的通信中共討論3個問題,而任意兩個科學家之間僅討論1個問題.證明:至少有3個科學家,他們彼此通信討論的是同一個問題.12.用一批1´2´4的長方體木塊,能不能把一個容積為6´6´6的正方體木箱充塞填滿?說明理由.13.在平面上有一個27´27的方格棋盤,在棋盤的正中間擺好81枚棋子,它們被罷成一個9´9的正方形.按下面的規(guī)則進行游戲:每一枚棋子都可沿水平方向或豎直方向越過相鄰的棋子,放進緊挨著這枚棋子的空格中,并把越過的這格棋子取出來.問:是否存在一

4、種走法,使棋盤上最后恰好剩下一枚棋子?14.12´12的超極棋盤上,一匹超級馬每步跳至3´4矩形的另一角(如圖).問能否從任一點出發(fā)遍歷每一格恰一次,再回到出發(fā)點(這種情況又稱馬有“回路”)?oo 二十、染色問題（二）(答案）第1道題答案： 不能.對房間染色,使最下面的兩個房間染成黑色,與黑色相鄰的房染成白色,則圖中有7個黑色房間和5個白色房間.如果要想不重復(fù)地走過每一個房間,黑色與白色房間數(shù)應(yīng)該相等.故題中的想法是不能實現(xiàn)的.第2道題答案： 不能.對展室進行染色,使相鄰兩房間分別是黑色和白色的.此時入口處展室的顏色與出口處展室的顏色是相同的,而不重復(fù)參觀完36個展室,入口

5、與出口展室的顏色應(yīng)該不相同.第3道題答案： 不能.對這16個城市進行黑白相間的染色,一種顏色有9個,另一種顏色有7個.而要不重復(fù)地走遍這16個城市,黑色與白色的個數(shù)應(yīng)該相等.第4道題答案： 如圖,對4´n長方形的各列分別染上黑色和白色.任一l形紙片所占的方格只有兩類:第一類占3黑1白,第二類占3白1黑.n個設(shè)第一類有a個,第二類有b個,因為涂有兩種顏色的方格數(shù)相等,故有3b+a=3a+b,即a=b,也就是說第一類與第二類相等,因此各種顏色的方格數(shù)都是4的倍數(shù),總數(shù)是8的倍數(shù),從而n是偶然.第5道題答案：將棋盤黑白相間染色,由“馬”的走法可知,放在黑點上的“馬”,只能吃放在某些白點上的

6、馬.整個棋盤上黑、白點的個數(shù)均為45,故可在45個黑點放上馬,它們是不能互吃的.第6道題答案：如圖的方式對棋盤染色.那么一個田字形蓋住1個或3個白格,而一個4´1的矩形蓋住2個白格.這樣一來一個田字和15個4´1的矩形能蓋住的白格數(shù)是一個奇數(shù),但上圖中的白格數(shù)是一個偶數(shù),因此一個田字形和15個4´1的矩形不能復(fù)蓋8´8的棋盤.第7道題答案：將棋盤里黑白相間涂色.一個田字形蓋住2個白格,一個t字形蓋住3個或1個白格.故1個田字和15個t字蓋住的白格數(shù)是一個奇數(shù),但棋盤上的白格數(shù)是一個偶數(shù).因此一個田字形和15個t字形不能蓋住8´8的棋盤.第8道題

7、答案：將棋盤黑白相間地染色后,馬的走法是從一種顏色的格子跳到另一種顏色.棋盤上有32個白格與32個黑格,故馬可能跳遍整個棋盤.圖中給出了一種走法.56415835503960334744554059345138425746493653326145484354316237522053063221116132964214171425106192278231215128718326924第9道題答案：先對4´4的棋盤黑白相間的涂色(如圖),這道題的實際問題是問7個1´2矩形能否分別復(fù)蓋剪去a、b；剪去a、c；剪去a、d的三個棋盤.若7個1´2矩形可以復(fù)蓋剪殘的棋盤,因為

8、每個1´2矩形均可蓋住一個白格和一個黑格,所以棋盤的白格與黑格數(shù)目應(yīng)該相等.都是7個.而剪去a格和c格的棋盤(2)有5個白格8個黑格,剪去a、d的棋盤(3)有5個白格8個黑格,因此這兩個剪損的棋盤均不能被7個1´2矩形復(fù)蓋,也就不能剪成7個1´2的矩形.abcd棋盤(1)可以被7個1´2的矩形所復(fù)蓋.下面給出一種剪法:a11277b265436543第10道題答案：在第一行的7格中必有4格同色,不妨設(shè)這4格位于前4個位置,且均為紅色.然后考慮前4列構(gòu)成的3´4矩形.若第二行和第3行中出現(xiàn)2個或2個以上的紅色格子.則該行的兩個紅色格子與第一行的紅

9、色格子就組成一個4角同為紅色格子的矩形.若不然,則第2、3行中都至少有3個藍格在前4列中,不妨設(shè)第2行前3格為藍色,顯然第三行中的前3格中至少有2個藍格，故在二、三行的前4列中必存在四角都是藍色的矩形.第11道題答案：將17個科學家用17個點代表,兩點之間連結(jié)的線段表示兩個科學家之間討論的問題.用三種顏色給這些線段染色,表示三個問題,于是問題就變成:給17個點之間的所有連結(jié)線段用三種顏色染色,必有同色三角形.從任意一點,不妨設(shè)從a向其他16點a1,a2,a16共可連成16條線段,用三種顏色染色,由抽屜原則可知,必有6條線段同色.設(shè)這6條線段為aa1,aa2,aa6且同為紅色.考慮a1,a2,a

10、3,a4,a5,a6這六點之間的連線,若有一條為紅色,(如a1a2為紅色) ,則三角形aa1a2為紅色的同色三角形.aa1a2a3a4a5a6a1a2a3a4若這六點之間的連線中,沒有一條是紅色的,則它們之間只能涂兩種顏色.考慮從a1引出的五條線段a1a2 a1a3 a1a4 a1a5 a1a6,由抽屜原理知,其中必有三條是同色的.不妨設(shè)這三條為a1a2 a1a3 a1a4,且同為藍色.若三角形a2a3a4的三邊中有一條為藍色的,則有一個藍色的三角形存在;若三角形a2a3a4三邊都不是藍色的,則它的三邊是同為第三色的同色三角形.第12道題答案：把正方體木箱分成27個小正方體,每個小正方體的體積

11、為2´2´2=8.將這些正方體如右圖黑白相間染上色.顯然黑色2´2´2的正方體有14個,白色2´2´2小正方體有13個.每一個這樣的正方體相當于8個1´1´1的小正方體.將1´2´4的長方體放入木箱,無論怎么放,每個長方體木塊蓋住8個邊長為1的單位正方體,其中有4個黑色的,4個白色的.木箱共含6´6´6=216個單位正方體,26個長方體木塊共蓋住8´26=208個單位正方體,其中黑白各占104個,余下216-208=8個單位正方體是黑色的.但是第27個1´

12、2´4長方體木塊不管怎樣放,也無法蓋住這8個黑色單位正方體.第13道題答案：如圖,將整個棋盤的每一格都分別染上紅、白、黑三種顏色,這種染色方式將棋盤分成了三個部分.按照游戲規(guī)則,每走一步,有兩種顏色方格中的棋子數(shù)分別減少了1個,而第三種顏色的棋子數(shù)增加了一個.這表明每走一步,每個部分的棋子的奇偶性要發(fā)生改變.因為一開始時,81枚棋子擺成一個9´9的正方形,顯然三個部分的棋子數(shù)是相同的,從而每走一步,三部分中的棋子數(shù)的奇偶性是相同的.如果走了若干步以后,棋盤上恰好剩下一枚棋子,則兩部分上的棋子數(shù)為偶數(shù),而另一部分上的棋子數(shù)為奇數(shù).這種結(jié)果是不可能出現(xiàn)的.第14道題答案：用兩種方法對超級棋盤染色.首先,將棋盤黑白相間染色,則馬每跳一步,它所在的方格就要改變一次顏色.