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

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

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


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

 
最新文章
 
关注教师心理健康,做快乐教师!
来看看你的打腿技术合格吗?
自由泳手臂交叉技术
自由泳提速,肩部水感特别重要
二 找规律填数
“圳”式长寿秘诀曝光!深圳宝安6位百岁老.
 
随机阅读
 
关注教师心理健康,做快乐教师!
来看看你的打腿技术合格吗?
黄静雯《认识图形》观课反思
自由泳手臂交叉技术
自由泳提速,肩部水感特别重要
二 找规律填数
 
推荐文章
 
参加2017年深圳市“体彩杯”成人游泳锦.
2014年夏游记录
2012-2013年度冬泳记录

9月
22 2020
 

第12讲 染色和赋值


   作者:蓝忠诚 发表时间-21 :40:3  阅读( 7 )| 评论( 0 )

第12染色和赋值

  染色方法和赋值方法是解答数学竞赛问题的两种常用的方法。就其本质而言,染色方法是一种对题目所研究的对象进行分类的一种形象化的方法。而凡是能用染色方法来解的题,一般地都可以用赋值方法来解,只需将染成某一种颜色的对象换成赋于其某一数值就行了。赋值方法的适用范围要更广泛一些,我们可将题目所研究的对象赋于适当的数值,然后利用这些数值的大小、正负、奇偶以及相互之间运算结果等来进行推证。

一、染色法

  将问题中的对象适当进行染色,有利于我们观察、分析对象之间的关系。像国际象棋的棋盘那样,我们可以把被研究的对象染上不同的颜色,许多隐藏的关系会变得明朗,再通过对染色图形的处理达到对原问题的解决,这种解题方法称为染色法。常见的染色方式有:点染色、线段染色、小方格染色和对区域染色。

  例1 用15个“T”字形纸片和1个“田”字形纸片(如下图所示),能否覆盖一个8×8的棋盘?

  解:如下图,将 8×8的棋盘染成黑白相间的形状。如果15个“T”字形纸片和1个“田”字形纸片能够覆盖一个8×8的棋盘,那么它们覆盖住的白格数和黑格数都应该是32个,但是每个“T”字形纸片只能覆盖1个或3个白格,而1和3都是奇数,因此15个“T”字形纸片覆盖的白格数是一个奇数;又每个“田”字形纸片一定覆盖2个白格,从而15个“T”字形纸片与1个“田”字形纸片所覆盖的白格数是奇数,这与32是偶数矛盾,因此,用它们不能覆盖整个棋盘。

  例2 如左下图,把正方体分割成27个相等的小正方体,在中心的那个小正方体中有一只甲虫,甲虫能从每个小正方体走到与这个正方体相邻的6个小正方体中的任何一个中去。如果要求甲虫只能走到每个小正方体一次,那么甲虫能走遍所有的正方体吗?

  解:甲虫不能走遍所有的正方体。我们如右上图将正方体分割成27个小正方体,涂上黑白相间的两种颜色,使得中心的小正方体染成白色,再使两个相邻的小正方体染上不同的颜色。显然,在27个小正方体中,14个是黑的,13个是白的。甲虫从中间的白色小正方体出发,每走一步,方格就改变一种颜色。故它走27步,应该经过14个白色的小正方体、13个黑色的小正方体。因此在27步中至少有一个小正方体,甲虫进去过两次。由此可见,如果要求甲虫到每一个小正方体只去一次,那么甲虫不能走遍所有的小正方体。

  例3 8×8的国际象棋棋盘能不能被剪成7个2×2的正方形和9个4×1的长方形?如果可以,请给出一种剪法;如果不行,请说明理由。

  解:如下图,对8×8的棋盘染色,则每一个4×1的长方形能盖住2白2黑小方格,每一个2×2的正方形能盖住1白3黑或3白1黑小方格。推知7个正方形盖住的黑格总数是一个奇数,但图中的黑格数为32,是一个偶数,故这种剪法是不存在的。

  例4 在平面上有一个27×27的方格棋盘,在棋盘的正中间摆好81枚棋子,它们被摆成一个9×9的正方形。按下面的规则进行游戏:每一枚棋子都可沿水平方向或竖直方向越过相邻的棋子,放进紧挨着这枚棋子的空格中,并把越过的这枚棋子取出来。问:是否存在一种走法,使棋盘上最后恰好剩下一枚棋子?

  解:如下图,将整个棋盘的每一格都分别染上红、白、黑三种颜色,这种染色方式将棋盘按颜色分成了三个部分。按照游戏规则,每走一步,有两部分中的棋子数各减少了一个,而第三部分的棋子数增加了一个。这表明每走一步,每个部分的棋子数的奇偶性都要改变。

  因为一开始时,81个棋子摆成一个9×9的正方形,显然三个部分的棋子数是相同的,故每走一步,三部分中的棋子数的奇偶性是一致的。

  如果在走了若干步以后,棋盘上恰好剩下一枚棋子,则两部分上的棋子数为偶数,而另一部分的棋子数为奇数,这种结局是不可能的,即不存在一种走法,使棋盘上最后恰好剩下一枚棋子。

  例5 图1是由数字0,1交替构成的,图2是由图1中任选减1,如此反复多次形成的。问:图2中的A格上的数字是多少?

  解:如左下图所示,将8×8方格黑白交替地染色。

  此题允许右上图所示的6个操作,这6个操作无论实行在哪个位置上,白格中的数字之和减去黑格中的数字之和总是常数。所以图1中白格中的数字之和减去黑格中的数字之和,与图2中白格中的数字之和减去黑格中的数字之和相等,都等于32,由(31+A)-32=32,得出A=33。

  例6 有一批商品,每件都是长方体形状,尺寸是1×2×4。现在有一批现成的木箱,内空尺寸是6×6×6。问:能不能用这些商品将木箱填满?

  解:我们用染色法来解决这个问题。先将6×6×6的木箱分成216个小正方体,这216个小正方体,可以组成27个棱长为2的正方体。我们将这些棱长为2的正方体按黑白相间涂上颜色(如下图)。

  容易计算出,有14个黑色的,有13个白色的。现在将商品放入木箱内,不管怎么放,每件商品要占据8个棱长为1的小正方体的空间,而且其中黑、白色的必须各占据4个。现在白色的小正方体共有8×13=104(个),再配上104个黑色的小正方体,一共可以放26件商品,这时木箱余下的是8个黑色小正方体所占据的空间。这8个黑色的小正方体的体积虽然与一件商品的体积相等,但是容不下这件商品。因此不能用这些商品刚好填满。

  例7 6个人参加一个集会,每两个人或者互相认识或者互相不认识。证明:存在两个“三人组”,在每一个“三人组”中的三个人,或者互相认识,或者互相不认识(这两个“三人组”可以有公共成员)。

  证明:将每个人用一个点表示,如果两人认识就在相应的两个点之间连一条红色线段,否则就连一条蓝色线段。本题即是要证明在所得的图中存在两个同色的三角形。

  设这六个点为A,B,C,D,E,F。我们先证明存在一个同色的三角形:

  考虑由A点引出的五条线段AB,AC,AD,AE,AF,其中必然有三条被染成了相同的颜色,不妨设AB,AC,AD同为红色。再考虑△BCD的三边:若其中有一条是红色,则存在一个红色三角形;若这三条都不是红色,则存在一个蓝色三角形。

  下面再来证明有两个同色三角形:不妨设△ABC的三条边都是红色的。若△DEF也是三边同为红色的,则显然就有两个同色三角形;若△DEF三边中有一条边为蓝色,设其为DE,再考虑DA,DB,DC三条线段:若其中有两条为红色,则显然有一个红色三角形;若其中有两条是蓝色的,则设其为DA,DB。此时在EA,EB中若有一边为蓝色,则存在一个蓝色三角形;而若两边都是红色,则又存在一个红色三角形。

  故不论如何涂色,总可以找到两个同色的三角形。

二、赋值法

  将问题中的某些对象用适当的数表示之后,再进行运算、推理、解题的方法叫做赋值法。许多组合问题和非传统的数论问题常用此法求解。常见的赋值方式有:对点赋值、对线段赋值、对区域赋值及对其他对象赋值。

  例8 一群旅游者,从A村走到B村,路线如下图所示。怎样走才能在最短时间内到达B村?图中的数字表示走这一段路程需要的时间(单位:分)。

  解:我们先把从A村到各村的最短时间标注在各村的旁边,从左到右,一一标注,如下图所示。

  由此不难看出,按图中的粗黑线走就能在最短时间(60分钟)内从A村走到B村。

  例9 把下图中的圆圈任意涂上红色或蓝色。问:有无可能使得在同一条直线上的红圈数都是奇数?请说明理由。

  解:假设题中所设想的染色方案能够实现,那么每条直线上代表各点的数字之和便应都是奇数。一共有五条直线,把这五条直线上代表各点的数字之和的这五个奇数再加起来,得到的总和数仍应是一个奇数。但是,由观察可见,图中每个点都恰好同时位于两条直线上,在求上述总和数时,代表各点的数字都恰被加过两次,所以这个总和应是一个偶数。这就导致矛盾,说明假设不成立,染色方案不能实现。

  例10 平面上n(n≥2)个点A1,A2,…,An顺次排在同一条直线上,每点涂上黑白两色中的某一种颜色。已知A1和An涂上的颜色不同。证明:相邻两点间连接的线段中,其两端点不同色的线段的条数必为奇数。

  证明:赋予黑点以整数值1,白点以整数值2,点Ai以整数

  值为ai,当Ai为黑点时,ai=1,当Ai为白点时,ai=2。再赋予线段AiAi+1以整数值ai+ai+1,则两端同色的线段具有的整数值为2或4,两端异色的线段具有的整数值为3。

  所有线段对应的整数值的总和为

  (a1+a2)+(a2+a3)+(a3+a4)+…+(an-1+an)

  =a1+an+2(a2+a3+…+an-1)

  =2+1+2(a2+a3+…+an-1)=奇数。

  设具有整数值2,3,4的线段的条数依次为l,m,n,则

  2l+m+4n=奇数。

  由上式推知,m必为奇数,证明完毕。

  例11 下面的表1是一个电子显示盘,每一次操作可以使某一行四个字母同时改变,或者使某一列四个字母同时改变。改变的规则是按照英文字母的顺序,每个英文字母变成它的下一个字母(即A变成B,B变成C……Z变成A)。问:能否经过若干次操作,使表1变为表2?如果能,请写出变化过程,如果不能,请说明理由。

  S O B R  K B D S

  T Z F P   H E X G

  H O C N   R T B S

  A D V X   C F Y A

   表1     表2

  解:不能。将表中的英文字母分别用它们在字母表中的序号代替(即A用1,B用2……Z用26代替)。这样表1和表2就分别变成了表3和表4。

  每一次操作中字母的置换相当于下面的置换:

  1→2,2→3,…,25→26,26→1。

  19  15 2 18

  20  26 6 16

  8   15  3 14

  1   4  22 24

    表3

  11 2 4 19

  8  5 24 7

  18 20  2 19

  3 6 25  1

    表4

  容易看出,每次操作使四个数字改变了奇偶性,而16个数字的和的奇偶性没有改变。因为表3中16个数字的和为213,表4中16个数字的和为174,它们的奇偶性不同,所以表3不能变成表4,即表1不能变成表2。

  12 如图(1)~(6)所示的六种图形拼成右下图,如果图(1)必须放在右下图的中间一列,应如何拼?

  解:把右上图黑、白相间染色(见上图)。其中有11个白格和10个黑格,当图形拼成后,图形(2)(4)(5)(6)一定是黑、白各2格,而图形(3)必须有3格是同一种颜色,另一种颜色1格。因为前四种图形,黑、白已各占2×4=8(格),而黑格总共只有10格,所以图形(3)只能是3白1黑。由此知道图(1)一定在中间一列的黑格,而上面的黑格不可能,所以图(1)在中间一列下面的黑格中。

  那么其它图形如何拼呢?为了说明方便,给每一格编一个数码(见左下图)。


  因为图(3)是3白1黑,所以为使角上不空出一格,它只能放在(1,3,4,5)或(7,12,13,17)或(11,15,16,21)这三个位置上。

  若放在(1,3,4,5)位置上,则图(6)只能放在(7,12,13,18)或(15,16,19,20)或(2,7,8,13)这三个位置,但是前两个位置是明显不行的,否则角上会空出一格。若放在(2,7,8,13)上,则图(2)只能放在(12,17,18,19)位置上,此时不能同时放下图(4)和图(5)。

  若把图(3)放在(7,12,13,17)位置上,则方格1这一格只能由图(2)或图(6)来占据。如果图(2)放在(1,2,3,4),那么图(6)无论放在何处都要出现孤立空格;如果把图(6)放在(1,4,5,10),那么2,3这两格放哪一图形都不合适。

  因此,图形(3)只能放在(11,15,16,21)。其余图的拼法如右上图。



上一篇文章:2020年夏泳45    下一篇文章:“清粉”陷阱!这项服务病毒式传播 相关软件潜藏巨大风险



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