1、二十 染色问题(1)年级 班 姓名 得分 (编者按 :由于内容本身的限制,本讲不设填空题 )1.某影院有 31 排,每排 29 个座位.某天放映了两场电影,每个座位上都坐了一个观众.如果要求每个观众在看第二场电影时必须跟他(前、后、左、右)相邻的某一观众交换座位,这样能办到吗?为什么? 2.如图是一所房子的示意图,图中数字表示房间号码,每间房子都与隔壁的房间相通.问能否从 1 号房间开始,不重复的走遍所有房间又回到 1 号房间?1 2 34 5 67 8 93.在一个正方形的果园里,种有 63 棵果树、加上右下角的一间小屋,整齐地排列成八行八列( 见图 (a).守园人从小屋出发经过每一棵树 ,
2、不重复也不遗漏(不许斜走), 最后又回到小屋,行吗?如果有 80 棵果树,连小屋在内排成九行九列 (图(b)呢?(a) (b)4.一个 88 国际象棋(下图)去掉对角上两格后,是否可以用 31 个 21 的“骨牌” ( 形如 )把象棋盘上的 62 个小格完全盖住?5.如果在中国象棋盘上放了多于 45 只马,求证:至少有两只马可以 “互吃”.6.空间 6 个点,任三点不共线,对以它们为顶点的线段随意涂以红色或蓝色,是否必有两个同色三角形?7.如图,把正方体分割成 27 个相等的小正方体,在中心的那个小正方体中有一只甲虫,甲虫能从每个小正方体走到与这个正方体相邻的 6 个小正方体中的任一个中去.如
3、果要求甲虫能走到每个小正方体一次,那么甲虫能走遍所有的正方体吗?8.中国象棋的马走“ 日” 字, 车走横线或竖线,下图是半张中国象棋盘 ,试回答下面的问题:一只马从起点出发,跳了 n 步又回到起点.证明:n 一定是偶数 .9.中国象棋的马走“ 日” 字, 车走横线或竖线,下图是半张中国象棋盘 ,试回答下面的问题:一只马能否跳遍这半张棋盘,每一点都不重复,最后一步跳回起点?10.中国象棋的马走“ 日” 字 ,车走横线或竖线,下图是半张中国象棋盘 ,试回答下面的问题:A BA B证明:一只马不可能从位置 B 出发,跳遍半张棋盘而每个点都只经过一次(不要求最后一步跳回起点).11.中国象棋的马走“
4、日” 字 ,车走横线或竖线,下图是半张中国象棋盘 ,试回答下面的问题:一只马能否从位置 B 出发,用 6 步跳到位置 A?为什么?12.中国象棋的马走“ 日” 字 ,车走横线或竖线,下图是半张中国象棋盘 ,试回答下面的问题:一只车从位置 A 出发,在这半张棋盘上走,每步走一格 ,走了若干步后到了位置 B.证明 :至少有一个格点没被走过或被走了不止一次.13.88 的国际象棋棋盘能不能被剪成 7 个 22 的正方形和 9 个 41 的长方形?如果可以 ,请给出一种剪法 ;如果不行,请说明理由.14.(表 1)是由数字 0,1 交替构成的,(表 2)是由(表 1)中任选 、 、 三种形式组成的图形
5、,并在每个小方格全部加 1 或减 1,如此反复多次进行形成的,试问(表 2)中的 A 格上的数字是多少 ?并说明理由.1 0 1 0 1 0 1 00 1 0 1 0 1 0 11 0 1 0 1 0 1 00 1 0 1 0 1 0 01 0 1 0 1 0 1 00 1 0 1 0 1 0 11 0 1 0 1 0 1 00 1 0 1 0 1 0 1A BA BA B表 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 A 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1
6、1 1 1 1 1 1表 2答 案1. 把影院的座位图画成黑白相间的矩形.(2931),共有 899 个小方格.不妨假定四角为黑格,则共有黑格 450 个,白格 449 个.要求看第二场电影,每位观众必须跟他相邻的某一观众交换位置,即要求每一黑白格必须互换,因黑白格的总数不相等,因此是不可能的.2. 将编号为奇数的房间染成黑色,编号为偶数的房间染成白色.从 1 号房间出发,只能按黑 白 黑 白 的次序,当走遍九个房间时应在黑色房间中,这个房间不与 1 号房间相邻,故不能不重复地走遍所有房间又回到 1 号房间.3. 图(a)行,走法如图所示. 图(a)图(b)不行,将小屋染成黑色,果树染成黑白相
7、间的颜色,则图(b)中有 41 个黑色的,40 个白色的.从小屋出发,按黑 白 黑 白 的次序,当走遍80 棵树后,到达的树的颜色还是黑色,与小屋不相邻,故不可能最后回到小屋.4. 不能.原因是每一个 21 的矩形骨牌一定恰好盖住一个黑格和一个白格,31 个这样的骨牌恰好盖住 31 个黑格和 31 个白格.但是国际象棋棋盘上对角两格的颜色是相同的,把它们去掉后剩下的是 30个白格,32 个黑格,或 32 个白格,30 个黑格,因此不能盖住.5. 中国象棋棋盘上有 90 个交叉点,把棋盘分成 10 个小部分,每部分有33=9 个交叉点 ,由抽屉原则知,至少有一个小部分内含有 6 只马.将这一小部
8、分的 9 个交叉点分别涂上黑色及白色.总有两只马在不同颜色交叉点上,故一定有两只马“互吃”.6. 设这六个点为 A、B、C、D、E、F.我们先证明存在一个同色的三角形:考虑由 A 点引出的五条线段 AB、AC、AD、AE、 AF,其中必有三条被染成了相同的颜色,不妨设 AB、AC、AD 三条同为红色.再考虑三角形 BCD 的三边:若其中有一条为红色,则存在一个红色三角形;若这三条都不是红色 ,则三角形BCD 为蓝色三角形 .ABDC下面再来证明有两个同色三角形,不妨设三角形 ABC 的三边同为红色.(1) 若三角形 DEF 也是红色三角形,则存在两个同色三角形 .(2) 若三角形 DEF 中有
9、一条边为蓝色(不妨设 DE),下面考虑 DA、DB、DC三条线段，其中必有两条同色.若其中有两条是红色的,如 DA、DB 是红色的,则三角形 DAB 为第二个同色三角形(图 1).若其中有两条是蓝色的,设 DA、DB 为蓝色(图 2).此时在 EA、EB 两条线段中,若有一条为蓝色,则存在一个蓝色三角形;若两条都是红色的 ,则三角形 EAB为红色三角形.综上所述,一定有两个同色三角形.7. 甲虫不能走遍所有的立方体.我们将大正方体如图分割成 27 个小正方体,涂上黑白相间的两种颜色,使得中心的小正方体染成白色,再使两个相邻的小正方体染上不同的颜色.显然在 27个小正文体中,14 个是黑的,13
10、 个是白的.甲虫从中间的白色正方体出发,每走一步,小正方体就改变一种颜色.故它走 27 步,应该经过 14 个白色的小正方体,13 个黑色的小正方体.因此在 27 步中至少有一个白色的小正方体,甲虫进去过两次.故若要求甲虫到每个小正方体只去一次,甲虫就不能走遍所有的小正方体.8. 将棋盘上的各点按黑白相间的方式染上黑白二色.由“马步”的行走规则,当“马”从黑点出发,下一步只能跳到白点 ,以后依次是黑、白、黑、白要回到原出发点(黑点),它必须跳偶数步.9. 不能.半张象棋盘共有 45 个格点,马从起点出发跳遍半张棋盘,则起点与最后一步同色.故不可能从最后一步跳回起点.10. 与 B 点同色的点(
11、白点)有 22 个,异色的点(黑色)有 23 个.马从 B 点出发,跳AB CDE (图1)AB CDE (图2)了 42 步时,已经跳遍了所有的白色,还剩下两个黑点,但是马不能够连续跳过两个黑点.11. 不能.因为 A、B 两点异色,从 B 到 A 所跳的步数是一个奇数.12. “车”每走一步,所在的格点就会改变一次颜色.因 A、B 两点异色,故从A 到 B“车”走的步数是一个奇数.但半张棋盘共有 45 个格点,不重复地走遍半张棋盘要 44 步，但 44 是一个偶数.13. 如图对 88 的棋盘染色,则每一个 41 的长方形能盖住 2 白 2 黑小方格,而每一个 22 的正方形能盖住 1 白
12、 3 黑或 1 黑 3 白小方格,那么 7 个 22 的正方形盖住的黑色小方格数总是一个奇数,但图中黑格数为 32 是一个偶数.故这种剪法是不存在的.14. 如下图所示,将表(1)黑白相间地染色.表(1)本题条件允许如图所示的 6 个操作,这 6 个操作无论实行在那个位置上,白格中的数字之和减去黑格中的数字之和总是一个常数,所以表 1 中白格中数字之和与黑格中数字之和的差即 32,等于表 2 中白格中数字之和与黑格中数字之和的差即(31+A)-32,于是(31+A)-32=32,故 A=33.+1 +1+1 +1-1 -1-1 -1+1 +1+1 +1+1+1-1 -1-1 -1-1-1+1
13、+1+1 +1+1 +1-1 -1-1 -1-1 -1二十 染色问题(2)年级 班 姓名 得分 1. 下图是一套房子的平面图,图中的方格代表房间,每个房间都有通向任何一个邻室的门.有人想从某个房间开始,依次不重复地走遍每一个房间,他的想法能实现吗?2. 展览会有 36 个展室(如图),每两相邻展室之间均有门相通.能不能从入口进去,不重复地参观完全部展室后,从出口出来呢?3. 图中的 16 个点表示 16 个城市,两个点之间的连线表示这两个城市有公路相通.问能否找到一条不重复地走遍这 16 座城市的路线?4. 下图是由 4 个小方格组成的“L”形硬纸片,用若干个这种纸片无重叠地拼成一个 4n 的
14、长方形,试证明:n 一定是偶数.5.中国象棋盘上最多能放几只马互不相“吃”(“马”走“ 日”字,另不考虑“ 别马腿”的情况).6.能否用一个田字和 15 个 41 矩形覆盖 88 棋盘? 7.能否用 1 个田字和 15 个 T 字纸片,拼成一个 88 的正方形棋盘?8.在 88 棋盘上,马能否从左下角的方格出发,不重地走遍棋盘,最后回到起点?若能请找出一条路,若不能,请说明理由.9.下面三个图形都是从 44 的正方形分别剪去两个 11 的小方格得到的,问可否把它们分别剪成 12 的七个小矩形?(1) (2) (3) 10.把三行七列的 21 个小格组成的矩形染色,每个小格染上红、蓝两种色中的一
15、种.求证:总可以找到 4 个同色小方格,处于某个矩形的 4 个角上( 如图)红 红 红 红11.17 个科学家互相通信,在他们的通信中共讨论 3 个问题,而任意两个科学家之间仅讨论 1 个问题.证明:至少有 3 个科学家,他们彼此通信讨论的是同一个问题.12.用一批 124 的长方体木块,能不能把一个容积为 666 的正方体木箱充塞填满?说明理由 .13.在平面上有一个 2727 的方格棋盘,在棋盘的正中间摆好 81 枚棋子,它们被罢成一个 99 的正方形.按下面的规则进行游戏: 每一枚棋子都可沿水平方向或竖直方向越过相邻的棋子,放进紧挨着这枚棋子的空格中,并把越过的这格棋子取出来.问:是否存在一种走法,使棋盘上最后恰好剩下一枚棋子 ?14.1212 的超极棋盘上,一匹超级马每步跳至 34 矩形的另一角(如图).问能否从任一点出发遍历每一格恰一次,再回到出发点(这种情况又称马有“回路”)?OO123
