北京数学竞赛培训第12讲 染色和赋值


第 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?如果能, 请写出变化过程,如果不能,请说明理由。 SOBR KBDS

TZFP HOCN ADVX 表1

HEXG RTBS CFYA 表2

解:不能。将表中的英文字母分别用它们在字母表中的序号代替(即 A 用 1,B 用 2??Z 用 26 代替)。这样表 1 和表 2 就分别变成了表 3 和 表 4。 每一次操作中字母的置换相当于下面的置换: 1→2,2→3,?,25→26,26→1。 19 20 8 1 15 26 15 4 表3 11 8 18 3 2 5 20 6 25 表4 容易看出,每次操作使四个数字改变了奇偶性,而 16 个数字的和的 奇偶性没有改变。因为表 3 中 16 个数字的和为 213,表 4 中 16 个数字的 和为 174,它们的奇偶性不同,所以表 3 不能变成表 4,即表 1 不能变成 表 2。 例 12 如图(1)~(6)所示的六种图形拼成右下图,如果图(1) 必须放在右下图的中间一列,应如何拼? 4 24 2 19 7 19 1 2 6 3 22 18 16 14 24

解:把右上图黑、白相间染色(见上图)。其中有 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)。其余图的拼法如右 上图。

练习 12

1.中国象棋盘的任意位置有一只马,它跳了若干步正好回到原来的位 置。问:马所跳的步数是奇数还是偶数? 2.右图是某展览大厅的平面图,每相邻两展览室之间都有门相通。今 有人想从进口进去,从出口出来,每间展览厅都要走到,既不能重复也不 能遗漏,应如何走法?

3.能否用下图中各种形状的纸片(不能剪开)拼成一个边长为 99 的 正方形(图中每个小方格的边长为 1)?请说明理由。

4.用 15 个 1×4 的长方形和 1 个 2×2 的正方形,能否覆盖 8×8 的棋 盘? 5.平面上不共线的五点,每两点连一条线段,并将每条线段染成红色 或蓝色。 如果在这个图形中没有出现三边同色的三角形,那么这个图形一 定可以找到一红一蓝两个“圈”(即封闭回路),每个圈恰好由五条线段 组成。 6.将正方形 ABCD 分割成 n 个相等的小正方格,把相对的顶点 A,C 染成红色,B,D 染成蓝色,其他交点任意染成红、蓝两种颜色之一。试 说明:恰有三个顶点同色的小方格的数目是偶数。
2

7.已知△ABC 内有 n 个点,连同 A,B,C 三点一共(n+3)个点。 以这些点为顶点将△ABC 分成若干个互不重叠的小三角形。将 A,B,C 三点分别染成红色、蓝色和黄色。而三角形内的 n 个点,每个点任意染成 红色、蓝色和黄色三色之一。问:三个顶点颜色都不同的三角形的个数是 奇数还是偶数? 8.从 10 个英文字母 A,B,C,D,E,F,G,X,Y,Z 中任意选 5 个字母(字母允许重复)组成一个“词”,将所有可能的“词”按“字典 顺序”(即英汉辞典中英语词汇排列的顺序)排列,得到一个“词表”: AAAAA,AAAAB,?,AAAAZ,

AAABA,AAABB,?,ZZZZY,ZZZZZ。 设位于“词”CYZGB 与“词”XEFDA 之间(这两个词除外)的“词” 的个数是 k,试写出“词表”中的第 k 个“词”。 练习 12 1.偶数。 解: 把棋盘上各点按黑白色间隔进行染色 (图略) 。 马如从黑点出发, 一步只能跳到白点,下一步再从白点跳到黑点,因此,从原始位置起相继 经过:白、黑、白、黑??要想回到黑点,必须黑、白成对,即经过偶数 步,回到原来的位置。 2.不能。 解:用白、黑相间的方法对方格进行染色(如图)。若满足题设要求 的走法存在, 必定从白色的展室走到黑色的展室,再从黑色的展室走到白 色的展室,如此循环往复。现共有 36 间展室,从白色展室开始,最后应 该是黑色展室。但右图中出口处的展室是白色的,矛盾。由此可以判定符 合要求的走法不存在。

3.不能。 解:我们将 99×99 的正方形中每个单位正方形方格染上黑色或白 色,使每两个相邻的方格颜色不同,由于 99×99 为奇数,两种颜色的方 格数相差为 1。而每一种纸片中,两种颜色的方格数相差数为 0 或 3,如 果它们能拼成一个大正方形, 那么其中两种颜色之差必为 3 的倍数。 矛盾! 4.不能。 解:如图,给 8×8 的方格棋盘涂上 4 种不同的颜色(用数字 1,2, 3,4 表示)。显然标有 1,2,3,4 的小方格各有 16 个。每个 1×4 的长 方形恰好盖住标有 1,2,3,4 的小方格各一个,但一个 2×2 的正方形只 能盖住有三种数字的方格,故无法将每个方格盖住,即不可能有题目要求 的覆盖。

5.证:设五点为 A,B,C,D,E。考虑从 A 点引出的四条线段:如 果其中有三条是同色的,如 AB,AC,AD 同为红色,那么△BCD 的三边 中,若有一条是红色,则有一个三边同为红色的三角形;若三边都不是红 色,则存在一个三边同为蓝色的三角形。这与已知条件是矛盾的。

所以,从 A 点出发的四条线段,有两条是红色的,也有两条是蓝色 的。当然,从其余四点引出的四条线段也恰有两条红色、两条蓝色,整个 图中恰有五条红色线段和五条蓝色线段。 下面只看红色线段,设从 A 点出发的两条是 AB,AE。再考虑从 B 点出发的另一条红色线段,它不应是 BE,否则就有一个三边同为红色的 三角形。不妨设其为 BD。再考虑从 D 点出发的另一条红色线段,它不应 是 DE,否则从 C 引出的两条红色线段就要与另一条红色线段围成一个红 色三角形,故它是 DC。最后一条红色线段显然是 CE。这样就得到了一 个红色的“圈”:

A→B→D→C→E→A。 同理,五条蓝线也构成一个“圈”。

6.证:将红点赋值为 0,蓝点赋值为 1。再将小方格四顶点上的数的 和称为这个小方格的值。若恰有三顶点同色,则该小方格的值为奇数,否 则为偶数。在计算所有 n2 个小方格之值的和时,除 A,B,C,D 只计算 一次外,其余各点都被计算了两次或四次。因为 A,B,C,D 四个点上 的数之和是偶数,所以 n2 个小方格之值的和是偶数,从而这 n2 个值中有 偶数个奇数。 7.奇数。 解:先对所有的小三角形的边赋值:边的两端点同色,该线段赋值为 0,边的两端点不同色,该线段赋值为 1。 然后计算每个小三角形的三边赋值之和,有如下三种情况: (1)三个顶点都不同色的三角形,赋值和为 3; (2)三个顶点中恰有两个顶点同色的三角形,赋值和为 2; (3)三个顶点同色的三角形,赋值和为 0。 设所有三角形的边赋值总和为 S,又设(1)(2)(3)三类小三角 形的个数分别为 a,b,c,于是有 S=3a+2b+0c=3a+2b。(*) 注意到在所有三角形的边赋值总和中,除了 AB,BC,CA 三条边外, 都被计算了两次, 故它们的赋值和是这些边赋值和的 2 倍, 再加上△ABC 的三边赋值和 3,从而 S 是一个奇数,由(*)式知 a 是一个奇数,即三 个顶点颜色都不同的三角形的个数是一个奇数。 8.EFFGY。 解:将 A,B,C,D,E,F,G,X,Y,Z 分别赋值为 0,1,2,3, 4,5,6,7,8,9,则 CYZGB=28961,_XEFDA=74530。 在 28961 与 74530 之间共有 74530-28961-1=45568(个)数,词表中 第 45568 个词是 EFFGY。


相关文档

更多相关文档

第12讲 染色和赋值
数学奥林匹克专题讲座 第12讲 染色和赋值
初一数学竞赛培训第12讲-提高训练
2011年北京市数学竞赛辅导第18讲数学方法选讲(下)
初中数学竞赛培训讲义-第十二讲__与矩形、菱形、正方形、梯形相关的竞赛题
2011年北京市数学竞赛辅导第10讲应用问题选讲
北京市第十二届数学竞赛试题
2011年北京市数学竞赛辅导第07讲图形与面积
自主招生试卷北京培训项目真题解析第12讲 反三角函数
新课标八年级数学竞赛培训第12讲:等腰三角形的判定
2012江苏省数学竞赛《提优教程》教案:第14讲 染色问题
北京数学竞赛培训第09讲 列方程解应用题
2012江苏省数学竞赛《提优教程》第58讲 二项式定理
2012江苏省数学竞赛《提优教程》教案:第36讲__同_余
2012江苏省数学竞赛《提优教程》教案:第73讲_不等式证明选讲
电脑版