六年級奧數專題01：染色問題

1、二十 染色問題(1) 年級 班 姓名 得分 (編者按:由于內容本身的限制,本講不設填空題) 1.某影院有31排,每排29個座位.某天放映了兩場電影,每個座位上都坐了一個觀眾.如果要求每個觀眾在看第二場電影時必須跟他(前、后、左、右)相鄰的某一觀眾交換座位,這樣能辦到嗎?為什么? 2.如圖是一所房子的示意圖,圖中數字表示房間號碼,每間房子都與隔壁的房間相通.問能否從1號房間開始,不重復的走遍所有房間又回到1號房間?1234567893.在一個正方形的果園里,種有63棵果樹、加上右下角的一間小屋,整齊地排列成八行八列(見圖 (a).守園人從小屋出發(fā)經過每一棵樹,不重復也不遺漏(不許斜走),最后又回

2、到小屋,行嗎?如果有80棵果樹,連小屋在內排成九行九列(圖(b)呢? (a) (b)4.一個8´8國際象棋(下圖)去掉對角上兩格后,是否可以用31個2´1的“骨牌” (形如 )把象棋盤上的62個小格完全蓋住?5.如果在中國象棋盤上放了多于45只馬,求證:至少有兩只馬可以“互吃”.6.空間6個點,任三點不共線,對以它們?yōu)轫旤c的線段隨意涂以紅色或藍色,是否必有兩個同色三角形?7.如圖,把正方體分割成27個相等的小正方體,在中心的那個小正方體中有一只甲蟲,甲蟲能從每個小正方體走到與這個正方體相鄰的6個小正方體中的任一個中去.如果要求甲蟲能走到每個小正方體一次,那么甲蟲能走遍所有的

3、正方體嗎?8.中國象棋的馬走“日”字,車走橫線或豎線,下圖是半張中國象棋盤,試回答下面的問題:AB一只馬從起點出發(fā),跳了n步又回到起點.證明:n一定是偶數.9.中國象棋的馬走“日”字,車走橫線或豎線,下圖是半張中國象棋盤,試回答下面的問題:AB一只馬能否跳遍這半張棋盤,每一點都不重復,最后一步跳回起點?10.中國象棋的馬走“日”字,車走橫線或豎線,下圖是半張中國象棋盤,試回答下面的問題:AB證明:一只馬不可能從位置B出發(fā),跳遍半張棋盤而每個點都只經過一次(不要求最后一步跳回起點).11.中國象棋的馬走“日”字,車走橫線或豎線,下圖是半張中國象棋盤,試回答下面的問題:AB一只馬能否從位置B出發(fā),

4、用6步跳到位置A?為什么?12.中國象棋的馬走“日”字,車走橫線或豎線,下圖是半張中國象棋盤,試回答下面的問題:AB一只車從位置A出發(fā),在這半張棋盤上走,每步走一格,走了若干步后到了位置B.證明:至少有一個格點沒被走過或被走了不止一次.13.8´8的國際象棋棋盤能不能被剪成7個2´2的正方形和9個4´1的長方形?如果可以,請給出一種剪法;如果不行,請說明理由.14.(表1)是由數字0,1交替構成的,(表2)是由(表1)中任選 、 、 三種形式組成的圖形,并在每個小方格全部加1或減1,如此反復多次進行形成的,試問(表2)中的A格上的數字是多少?并說明理由.10101

5、01001010101101010100101010010101010010101011010101001010101 表 111111111111111111111111111111111111111A1111111111111111111111111 表 2答 案 1. 把影院的座位圖畫成黑白相間的矩形.(29´31),共有899個小方格.不妨假定四角為黑格,則共有黑格450個,白格449個. 要求看第二場電影,每位觀眾必須跟他相鄰的某一觀眾交換位置,即要求每一黑白格必須互換,因黑白格的總數不相等,因此是不可能的.2. 將編號為奇數的房間染成黑色,編號為偶數的房間染成白色.從1號

6、房間出發(fā),只能按黑 白 黑 白 的次序,當走遍九個房間時應在黑色房間中,這個房間不與1號房間相鄰,故不能不重復地走遍所有房間又回到1號房間.3. 圖(a)行,走法如圖所示. 圖(a)圖(b)不行,將小屋染成黑色,果樹染成黑白相間的顏色,則圖(b)中有41個黑色的,40個白色的.從小屋出發(fā),按黑 白 黑 白 的次序,當走遍80棵樹后,到達的樹的顏色還是黑色,與小屋不相鄰,故不可能最后回到小屋.4. 不能.原因是每一個2´1的矩形骨牌一定恰好蓋住一個黑格和一個白格,31個這樣的骨牌恰好蓋住31個黑格和31個白格.但是國際象棋棋盤上對角兩格的顏色是相同的,把它們去掉后剩下的是30個白格,3

7、2個黑格,或32個白格,30個黑格,因此不能蓋住.5. 中國象棋棋盤上有90個交叉點,把棋盤分成10個小部分,每部分有3´3=9個交叉點,由抽屜原則知,至少有一個小部分內含有6只馬.將這一小部分的9個交叉點分別涂上黑色及白色.總有兩只馬在不同顏色交叉點上,故一定有兩只馬“互吃”.6. 設這六個點為A、B、C、D、E、F.我們先證明存在一個同色的三角形:考慮由A點引出的五條線段AB、AC、AD、AE、AF,其中必有三條被染成了相同的顏色,不妨設AB、AC、AD三條同為紅色.再考慮三角形BCD的三邊:若其中有一條為紅色,則存在一個紅色三角形;若這三條都不是紅色,則三角形BCD為藍色三角形

8、.ABDC下面再來證明有兩個同色三角形,不妨設三角形ABC的三邊同為紅色.(1) 若三角形DEF也是紅色三角形,則存在兩個同色三角形.(2) 若三角形DEF中有一條邊為藍色(不妨設DE),下面考慮DA、DB、DC三條線段，其中必有兩條同色.ABCDE(圖2)ABCDE(圖1) 若其中有兩條是紅色的,如DA、DB是紅色的,則三角形DAB為第二個同色三角形(圖1).若其中有兩條是藍色的,設DA、DB為藍色(圖2).此時在EA、EB兩條線段中,若有一條為藍色,則存在一個藍色三角形;若兩條都是紅色的,則三角形EAB為紅色三角形.綜上所述,一定有兩個同色三角形. 7. 甲蟲不能走遍所有的立方體.我們將大

9、正方體如圖分割成27個小正方體,涂上黑白相間的兩種顏色,使得中心的小正方體染成白色,再使兩個相鄰的小正方體染上不同的顏色.顯然在27個小正文體中,14個是黑的,13個是白的.甲蟲從中間的白色正方體出發(fā),每走一步,小正方體就改變一種顏色.故它走27步,應該經過14個白色的小正方體,13個黑色的小正方體.因此在27步中至少有一個白色的小正方體,甲蟲進去過兩次.故若要求甲蟲到每個小正方體只去一次,甲蟲就不能走遍所有的小正方體.8. 將棋盤上的各點按黑白相間的方式染上黑白二色.由“馬步”的行走規(guī)則,當“馬”從黑點出發(fā),下一步只能跳到白點,以后依次是黑、白、黑、白要回到原出發(fā)點(黑點),它必須跳偶數步.

10、9. 不能.半張象棋盤共有45個格點,馬從起點出發(fā)跳遍半張棋盤,則起點與最后一步同色.故不可能從最后一步跳回起點.10. 與B點同色的點(白點)有22個,異色的點(黑色)有23個.馬從B點出發(fā),跳了42步時,已經跳遍了所有的白色,還剩下兩個黑點,但是馬不能夠連續(xù)跳過兩個黑點.11. 不能.因為A、B兩點異色,從B到A所跳的步數是一個奇數.12. “車”每走一步,所在的格點就會改變一次顏色.因A、B兩點異色,故從A到B“車”走的步數是一個奇數.但半張棋盤共有45個格點,不重復地走遍半張棋盤要44步，但44是一個偶數.13. 如圖對8´8的棋盤染色,則每一個4´1的長方形能蓋住

11、2白2黑小方格,而每一個2´2的正方形能蓋住1白3黑或1黑3白小方格,那么7個2´2的正方形蓋住的黑色小方格數總是一個奇數,但圖中黑格數為32是一個偶數.故這種剪法是不存在的.+1+1+1+1-1-1-1-1+1+1+1+1+1+1-1-1-1-1-1-1-1-1+1+1+1+1+1+1-1-1-1-1-1-1 14. 如下圖所示,將表(1)黑白相間地染色. 表(1) 本題條件允許如圖所示的6個操作,這6個操作無論實行在那個位置上,白格中的數字之和減去黑格中的數字之和總是一個常數,所以表1中白格中數字之和與黑格中數字之和的差即32,等于表2中白格中數字之和與黑格中數字之和的

12、差即(31+A)-32,于是(31+A)-32=32,故A=33.二十 染色問題(2) 年級 班 姓名 得分 1. 下圖是一套房子的平面圖,圖中的方格代表房間,每個房間都有通向任何一個鄰室的門.有人想從某個房間開始,依次不重復地走遍每一個房間,他的想法能實現嗎?2. 展覽會有36個展室(如圖),每兩相鄰展室之間均有門相通.能不能從入口進去,不重復地參觀完全部展室后,從出口出來呢?3. 圖中的16個點表示16個城市,兩個點之間的連線表示這兩個城市有公路相通.問能否找到一條不重復地走遍這16座城市的路線?hhhhhhhhhhhhhhhh4. 下圖是由4個小方格組成的“L”形硬紙片,用若干個這種紙片

13、無重疊地拼成一個4´n的長方形,試證明:n一定是偶數.5.中國象棋盤上最多能放幾只馬互不相“吃”(“馬”走“日”字,另不考慮“別馬腿”的情況). 6.能否用一個田字和15個4´1矩形覆蓋8´8棋盤?7.能否用1個田字和15個T字紙片,拼成一個8´8的正方形棋盤?8.在8´8棋盤上,馬能否從左下角的方格出發(fā),不重地走遍棋盤,最后回到起點?若能請找出一條路,若不能,請說明理由.9.下面三個圖形都是從4´4的正方形分別剪去兩個1´1的小方格得到的,問可否把它們分別剪成1´2的七個小矩形? (1) (2) (3) 10.把

14、三行七列的21個小格組成的矩形染色,每個小格染上紅、藍兩種色中的一種.求證:總可以找到4個同色小方格,處于某個矩形的4個角上(如圖)123紅紅紅紅11.17個科學家互相通信,在他們的通信中共討論3個問題,而任意兩個科學家之間僅討論1個問題.證明:至少有3個科學家,他們彼此通信討論的是同一個問題.12.用一批1´2´4的長方體木塊,能不能把一個容積為6´6´6的正方體木箱充塞填滿?說明理由.13.在平面上有一個27´27的方格棋盤,在棋盤的正中間擺好81枚棋子,它們被罷成一個9´9的正方形.按下面的規(guī)則進行游戲:每一枚棋子都可沿水平方向

15、或豎直方向越過相鄰的棋子,放進緊挨著這枚棋子的空格中,并把越過的這格棋子取出來.問:是否存在一種走法,使棋盤上最后恰好剩下一枚棋子?14.12´12的超極棋盤上,一匹超級馬每步跳至3´4矩形的另一角(如圖).問能否從任一點出發(fā)遍歷每一格恰一次,再回到出發(fā)點(這種情況又稱馬有“回路”)?OO答 案 1. 不能.對房間染色,使最下面的兩個房間染成黑色,與黑色相鄰的房染成白色,則圖中有7個黑色房間和5個白色房間.如果要想不重復地走過每一個房間,黑色與白色房間數應該相等.故題中的想法是不能實現的. 2. 不能.對展室進行染色,使相鄰兩房間分別是黑色和白色的.此時入口處展室的顏色與出

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

17、“馬”,只能吃放在某些白點上的馬.整個棋盤上黑、白點的個數均為45,故可在45個黑點放上馬,它們是不能互吃的.6. 如圖的方式對棋盤染色.那么一個田字形蓋住1個或3個白格,而一個4´1的矩形蓋住2個白格.這樣一來一個田字和15個4´1的矩形能蓋住的白格數是一個奇數,但上圖中的白格數是一個偶數,因此一個田字形和15個4´1的矩形不能復蓋8´8的棋盤.7. 將棋盤里黑白相間涂色.一個田字形蓋住2個白格,一個T字形蓋住3個或1個白格.故1個田字和15個T字蓋住的白格數是一個奇數,但棋盤上的白格數是一個偶數.因此一個田字形和15個T字形不能蓋住8´8的

18、棋盤.8. 將棋盤黑白相間地染色后,馬的走法是從一種顏色的格子跳到另一種顏色.棋盤上有32個白格與32個黑格,故馬可能跳遍整個棋盤.圖中給出了一種走法.564158355039603347445540593451384257464936533261454843543162375220530632211161329642141714251061922782312151287183269249. 先對4´4的棋盤黑白相間的涂色(如圖),這道題的實際問題是問7個1´2矩形能否分別復蓋剪去A、B；剪去A、C；剪去A、D的三個棋盤.若7個1´2矩形可以復蓋剪殘的棋盤,因為每

19、個1´2矩形均可蓋住一個白格和一個黑格,所以棋盤的白格與黑格數目應該相等.都是7個.而剪去A格和C格的棋盤(2)有5個白格8個黑格,剪去A、D的棋盤(3)有5個白格8個黑格,因此這兩個剪損的棋盤均不能被7個1´2矩形復蓋,也就不能剪成7個1´2的矩形.ABCD棋盤(1)可以被7個1´2的矩形所復蓋.下面給出一種剪法:A11277B26543654310. 在第一行的7格中必有4格同色,不妨設這4格位于前4個位置,且均為紅色.然后考慮前4列構成的3´4矩形.若第二行和第3行中出現2個或2個以上的紅色格子.則該行的兩個紅色格子與第一行的紅色格子就組

20、成一個4角同為紅色格子的矩形.若不然,則第2、3行中都至少有3個藍格在前4列中,不妨設第2行前3格為藍色,顯然第三行中的前3格中至少有2個藍格，故在二、三行的前4列中必存在四角都是藍色的矩形.11. 將17個科學家用17個點代表,兩點之間連結的線段表示兩個科學家之間討論的問題.用三種顏色給這些線段染色,表示三個問題,于是問題就變成:給17個點之間的所有連結線段用三種顏色染色,必有同色三角形.從任意一點,不妨設從A向其他16點A1,A2,A16共可連成16條線段,用三種顏色染色,由抽屜原則可知,必有6條線段同色.設這6條線段為AA1,AA2,AA6且同為紅色.考慮A1,A2,A3,A4,A5,A

21、6這六點之間的連線,若有一條為紅色,(如A1A2為紅色) ,則三角形AA1A2為紅色的同色三角形.AA1A2A3A4A5A6A1A2A3A4若這六點之間的連線中,沒有一條是紅色的,則它們之間只能涂兩種顏色.考慮從A1引出的五條線段A1A2 A1A3 A1A4 A1A5 A1A6,由抽屜原理知,其中必有三條是同色的.不妨設這三條為A1A2 A1A3 A1A4,且同為藍色.若三角形A2A3A4的三邊中有一條為藍色的,則有一個藍色的三角形存在;若三角形A2A3A4三邊都不是藍色的,則它的三邊是同為第三色的同色三角形.12. 把正方體木箱分成27個小正方體,每個小正方體的體積為2´2´2=8.將這些正方體如右圖黑白相間染上色.顯然黑色2´2´2的正方體有14個,白色2´2´2小正方體有13個.每一個這樣的正方體相當于8個1´1´