运动,不是生活的全部,但是生活的最高处
                     运动,不是生活的全部,但是生活的最高处

区空间  校空间  我的主页    照片   好友[文章  收藏   评论   留言     最新阅读     推荐文章 

自行车/6 |  游泳/18 |  奥数教材(转载)/23 |  我的学生/3 |  生活与保健/3 |  个人收藏/7 |  跑步/6 |  力量训练/3 |  奥数竞赛(转载)/4 |  羽毛球/2 | 
本博客空间统计:   7494 篇文章   71 个评论


博主说明:教师
姓名:蓝忠诚
学校:罗芳小学
空间等级:51 >
现有积分:44871
距离下一等级:1129分
空间排名:教师类 第17

 
最新文章
 
练习二十五
第25讲 推理问题(1)
练习二十四解答
练习二十四
80年前,我们曾经历过怎样的绝望
“跟屁虫”是什么东西?其实它是野外游泳必.
 
随机阅读
 
有哪些因素,会让你收藏的老酒贬值?
刘文典
练习二十五
第25讲 推理问题(1)
他是唯一被国际公认的军神,击毙击伤11万.
他原是国军名将,却成为主席的亲家,还被授.
 
推荐文章
 
参加2017年深圳市“体彩杯”成人游泳锦.
2014年夏游记录
2012-2013年度冬泳记录

1月
17 2020
 

四、简单染色问题


   作者:蓝忠诚 发表时间-15 :25:2  阅读( 59 )| 评论( 0 )

四、简单染色问题


  有很多同学喜欢画画,有的喜欢画人物,有的喜欢画花草,有的喜欢画水彩画,有的喜欢画油画.有一些画靠优美的线条取胜,也有一些画以绚丽的色彩夺目,然而很少有人知道在数学问题中也有一些与色彩有关.这就是所谓的染色问题.以下我们就介绍一些简单的染色问题。


例1 有一个5×5的方格棋盘,如图1所示,每一个小方格中有一只小甲虫,假定在同一时刻,所有小甲虫都爬到邻格中(横向与纵向的格,不能斜爬),问此时能否会出现空格?


分析与解 初看这个问题,似乎无从下手,但如果我们利用“染色”的手段,就会使问题简化,很轻松的得到正确答案.


  将5×5棋盘用黑白两种颜色相间染色,如图2所示,此时共有黑格13个,白色格12个.当每个小格中的甲虫同时爬向邻格时,即黑格中的甲虫爬到白格中,白格中的甲虫爬到黑格中,由于黑格比白格多一格,则原来白格中的甲虫爬到黑格后必空一格,所以该题的答案是肯定的。


例2 如图3所示,有五种不同的颜色分别使A、B、C、D、E染色,要求相邻两区域所染的颜色不同,求共有多少种不同的染色方法?


 




分析与解 首先我们设定一种染色顺序,不妨假定按A、B、C、D、E的顺序。


  由于A与D不相邻,则A与D的颜色可以相同,也可以不相同。


  (1)若A与D颜色相同,则此时,A有5种染色方式;B不能与A同色,故只有4种染色方式;而C不能与A、B同色,故只有3种染色方式;E不能与A、C同色,即也有3种染色方式,由乘法原理,共有5×4×3×3=180种不同的染色方式。


  (2)若A与D颜色不同时,A还是5种染色方式,B还是4种染色方式,C还是3种染色方式,而D此时与A、B、C的颜色都不同,所以只有两种染色方式,E不能与A、C、D同色,即也有2种染色方式,由乘法原理,共有:5×4×3×2×2=240种不同的染色方式。


  由以上分析,共有不同的染色方式为:


  5×4×3×3+5×4×3×2×2=420(种)


例3 马能否从半个棋盘上任一点出发,不重不漏地跳遍半个棋盘的所有点?


分析与解 由马走“日”的特点,我们将半个棋盘上的所有点进行红黑两种染色,即相邻的点染上不同的颜色如图4.设A点一类为黑点,相邻点则为红点.不难看出,马每跳一步都是从一种颜色点到另一种颜色点,即马在连续跳动时,两种颜色的点交错出现.如果马能不重不漏地跳遍半个棋盘,则两种颜色点的个数应当相同或马在起跳点所在的一类色点多一个。


  但如图4,将半个棋盘进行红、黑两种染色,A类点为22点,剩下一类点为23点,当马的起跳点为A类点时,是不可能不重不漏地跳遍半个棋盘的,即马不能从半个棋盘的任一点出发,不重不漏地跳遍半个棋盘。







例3 到此就解完了,但留下一个问题:如果马的起跳点是红点,是否可以不重不漏跳遍半个棋盘?


  这里的回答是肯定的,我们利用构造法,画出马从红点出发,不重不漏地跳遍半个棋盘路线(如图5).棋盘周围的数字是马跳动的序号,“1”为起跳点.由于棋盘的对称性及路线的中途可衔接性,故从任意红点出发都可不重不漏地跳遍半个棋盘.


例4 对世界上任何六个人来说,其中至少有三个人,他们要么互相都认识,要么互相都不认识,请说明这是为什么?


分析与解 把这个问题换一种叙述方式,在纸上画出六个点,表示六个人,如果两个人认识,就在代表这两个人的两点间联一条红色直线;如果两人不认识,就在代表这两个人的两点间联一条蓝色直线.这样,六个点中的任意两点之间总能联一条直线,不是红线就是蓝线。







  在六点中任取其中一点A,如图6,它与其他五点有五条联线,每一条联线或红或蓝,而根据抽屉原理,其中至少有三条线颜色相同,不妨设AC、AD和AE是三条蓝色的联线。


  CE、CD和ED三条联线中,只要有一条蓝色的,就会有一个三边都是蓝色的三角形出现.这说明有三个人互相都不相识.如果CE、CD和ED都不是蓝色的,那么三角形CDE三边颜色都是红色的,这说明有三个人互相都相识。


例5 证明:用15个1×4的长方形和一个2×2的正方形不能覆盖8×8的正方形。


  分析与证明 要证明这个问题,显然不能用尝试法,用15个1×4的长方形和一个2×2的正方形一种情况一种情况的去拼摆.因为即使你拼摆不出来,你也不能下否定结论.所以必须要寻求一种正确的方法.我们借助于染色,设法将8×8的正方形进行黑白染色,使黑格一样多,而使15个1×4长方形和一个2×2正方形所能覆盖的黑白格不一样。


  如果我们将8×8正方形黑白相间染色(如图7),那么1×4长方形能覆盖两黑两白,一个2×2正方形也能覆盖两黑两白,这样出现不了矛盾,不能说明问题,故我们采用如图8的染色方法,此时,图中黑白格数目还是一样多,即都是32个格.但是关于一个2×2正方形来说,只能覆盖三黑一白或三白一黑,而一个1×4长方形仍然覆盖两黑两白,这样 15个1×4长方形只能覆盖住30个黑格和30个白格,剩下的两个黑格和两个白格无法用一个2×2正方形覆盖.故通过图8的染色方法可以证明15个1×4长方形和一个2×2正方形不能覆盖8×8正方形.







例6 现有1,1,2,2,3,3,…,10,10共20个数.问能否将这些数排一行并满足两个1之间有一个数,两个2之间有两个数,两个3之间有三个数,……,两个10之间有十个数?证明你的结论。


分析与证明 这个问题的结论是否定的.我们仍然应用“染色”法。


  将这20个数所应占的20个位置进行黑白相间染色.如图9所示,白色位置和黑色位置各占10个.







  根据题意,两个奇数之间要有奇数个数,两个偶数之间要有偶数个数,则两个奇数所占的位置应为相同颜色的两个位置,而两个偶数所占的位置则为不同颜色的位置.那么一共10个偶数要占5个黑色位置和5个白色位置.剩下的10个奇数,要么占10个黑色位置,要么占10个白色位置.于是如果满足题设的要求,则需要15个白色位置和5个黑色位置或15个黑色位置和5个白色位置,这与白色位置和黑色位置各占10个相矛盾.故满足题设的排法不可能。


上一篇文章:练习三解答    下一篇文章:练习四



个人空间评论从2017年1月起采用实名制: