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

区空间  校空间  我的主页    照片   好友[文章  收藏   评论   留言     音乐     推荐文章 

自行车/5 |  游泳/14 |  奥数教材/23 |  苏教版小学数学课件 |  我的学生/2 |  生活与保健/1 |  个人收藏/4 |  跑步/4 |  力量训练/1 |  游泳消费记录 |  奥数竞赛/1 | 
本博客空间统计:   5259 篇文章   71 个评论

加为好友  发送信息

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

 
最新文章
 
习题一答案
习题一
20181103-04活动记录
20181021夏泳58
20181020夏泳57
20181014夏泳56
 
随机阅读
 
《图形的运动与位置》复习课
习题一答案
习题一
天天蛋糕店
罗湖教育“停课不停学” 数学 四年级 第.
20181103-04活动记录
 
推荐文章
 
参加2017年深圳市“体彩杯”成人游泳锦.
2014年夏游记录
2012-2013年度冬泳记录

1月
17 2020
 

四、简单染色问题


   作者:蓝忠诚 发表时间-15 :25:2  阅读( 14 )| 评论( 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月起采用实名制:
深圳市罗湖区教育局 版权所有
地址:深圳市文锦中路螺岭小学综合楼7楼