专题4.2 染色或赋值+刘子琳.docx

《专题4.2 染色或赋值+刘子琳.docx》由会员分享，可在线阅读，更多相关《专题4.2 染色或赋值+刘子琳.docx（6页珍藏版）》请在课桌文档上搜索。

1、4.2染色或赋值在解决这些组合问题时，有时需要将具有共同性质的点，线，区域等进行染色或者赋值，从 而达到解决问题的目的，通常是将所研究的对象先进行分类，每一类用相同颜色或者赋权重 等，以更加形象地突出每一类的特点.这类方法本质上仍然是一种分类方法，只不过技巧性相对更强.下面通过一些例子来说明技 巧.1.已知：在5行7列的棋盘中挖去第一行，第4列上的小方格，试问：能否用1x2的豉头铺 满余下的34个格子.【解】如图4-2-1,对棋盘进行黑白交错染色，挖去第4列第一个后，还剩余18个黑格子与16个白格子，所以不能用17个砖块铺满棋盘且不重叠.【注】这是颜色问题中典型的区域小方格染色问题，所采用的也

2、是交错染色法.例2已知：在7x7的棋盘中有一只跳跳虫，最开始它位于第1行第2列的位置，跳跳虫只 能跳到与它所有格有临边的格子中，试问：跳跳虫能否不重复第经过棋盘每个格子一次？【解】如图42-2,将棋盘进行黑白交叉染色，跳跳虫刚开始到白格子里，要么跳白格子到 黑格子，所以若要不重复地经历所有格子各一次，必须有25个白格和24个黑格，而实际上 图中25个黑格和24个白格，要不重复地经历所有格子各一次例3证明：用15块大小相同为4x1的矩形瓷砖中和1块大小为2x2的正方形瓷砖，不能 恰好铺盖8x8的正方形地面.【分析】将8x8的正方形地面的方格一半染上一种颜色，另一种半染上一种颜色，在用4x1 的矩

3、形和2x2的正方形瓷砖去盖，如果盖去的两个颜色的大小方格不是一样多，那么说明 给定条件下完铺满不可能.【证明】如图4-2-3,用间隔为两格且与从右上至左下的这类次对角线平行的斜格染色方式,黑格和白格共有32个，由于4x1的矩形砖不论是横放还是竖盖，且无论盖在何处，总是占 据地面上的两个白格，两个黑格，从而15块4x1的矩形铺盖后还剩两个黑格和白格，但由 于与次对角线平行的斜格总是同色，而与主对角线平平行的相邻格总是异色，所以，不论怎 样放置，一块2x2的正方形砖，总是盖不住剩下的二黑二白的地面.例4如图4-2-4所示是一个由4个1X1的正方形组成的L形,若用干个这种L形硬纸片可以 重叠拼成机X

4、（长为加个单位，宽为个单位得矩形），试证明，7 必是8的倍数.m【证明】因为机X的矩形L形硬纸片可以重叠拼成，所以机X 是4的倍数，于是 必 是偶数.不妨设为机，把mx矩形中的加列按一列黑，一列白间隔染色，则不论L形在这 矩形中放置位置如何（L形共有8种可能）L形或占有3白一黑四个方格中（第一种）或 占有3黑一白四个方格中 设第一种L形共有P个，第二种L形共有4个，则ZX矩形中臼格子数为3p + q,而他的黑格子个数为p +3g由于为偶数，所以2X 矩形中黑白条数相同，黑、白方格总数也相同，从而有3p + q, = p + 3q,进而=夕,所以L形共有2p个，即L形总数有偶数个，相必是8的倍数

5、.例5能否把1,122,3,3, .,2010,2010这些数排成一行，使得两个1之间夹着一个数，两个之间夹着两个数，两个2010之间夹着2010个数，证明你的结论.【解】将2010x2个位置按奇数位着白色，偶数位着黑色染色，于是白黑各有2010个，已 知同一偶数占据一个黑点和一个白点，同一个奇数要么占据一个白点，要么占据一个黑点, 于是1005个偶数中，占据白点A=IoO5个，黑点g=1005个，1005个奇数中，占据白 点4=2个，黑点名=26个，其中 + 8 = l（X）5,因此，共占白点数目为A = A+4 =1005 + 2。个，黑点数目8 =q+层=1005 + 28个，由于 +力

6、= IOO5,所以 W8从而4 B,这与黑，白各有IOlO个矛盾，故这种排法不可能.【注】如果将2010改为2012,结论如何.A例6已知空间六点，任意三点不共线，任意四点共面，成对连接它们的十五条线段，用红 色染色体或者蓝色(一条线段只染一种颜色)求证：无论怎样染色，总存在同色三角形.【证明】设A, BC D1E1F是所给六点，考虑以A为端点的线段有ABy AC, AD, AE, AF由 于抽屉原则可知，这五条线段中至少有三条颜色相同，不妨设A&AC,AO都染成红色，在 考虑ABCD的三边，如果其中一边是红色，则同色三角形已出现，如MCD的三边，如果 其中一边不是红色，则同色三角形已出现 故

7、无论哪种情况下，都存在同色三角形例7已知12个红球和12个篮球排成一行，证明：必有相邻的六个球为三红三蓝.【证明】将这些球上标上数字，红色球上标上L蓝色球上标上2,于是问题变为：必有6个 相邻的球，它们的标号之和为0,记为从第i个球起6个相邻数字之和为Sj y由于i可以取 1,2, 3,19中的每一个数，而现的所有取值为6 4 -2,024,6,且|5二 一周=0或2. 由5+57+号3 +豆9=0可知，若四个数中有0,则命题已成立.否则有正有负，不妨设Sj 0,Sj lt = 0,而(3 + % + /“)(4+4 + 力2)= (4+“2 + + 82”)2 另一方面，当生与2面对面时，。

8、也,42。+,。2/21中的1的个数表示这时的跳舞的个数，如果在整个过程中，每次跳舞的人数均少于对，那么恒有aibi + a2bM +%也T0(/ = l,2,.2n),2从而满足 01+ + )/=I由与矛盾，至少有一次跳舞的人数不少于对.【注】本题处理过程中用到从局部到整体处理的思想.练习4.2L如图，是由14个大小相同的方格组成的图形，证明：无论如何沿着图中格子线剪裁，总 不能剪出七个由相邻小方格组成的矩形.2.证明：在任意六个人中，必有三个互相认识或者不认识.4 .中国象棋的马，每步由1x2的格的一个顶点跳到其对角顶点，求证：该马从棋盘上任意一 点出发要跳到相邻的邻格，必须经过奇数步.

9、5 .能否用面积1 x4的一些长方块将IOXlO的棋盘覆盖？6 .已知三角形ABC内有个点(无三点共线)，连同A,B,C共，2 + 3个点，以把这些点把三 角形ABC分成若干个互不重叠的小三角形，现把AB,C分别染成红色、蓝色、黄色，而 其余个点，每个点必须染上红色、蓝色、黄色之一，求证：三顶点都不同色的小三角形的 总数必是奇数.小三角形的面积Lx立二立.3 4127 .考虑这些5个数字之和的最值，显然最小为4x5 = 20,最大为6x5 = 30.所以取值共有11 种可能，即11个抽屉，而每行，每列。两条对角线共12个和，放入11个抽屉，必有一个 抽屉有两个和，即必有两个和是相等的，所以，无

10、法做到各不相同.8 .将所有可能的长方形按面积从小到大写出如下：1 1,1 2,1 3,1 4,2 2,1 5,1 6,2 3,1 7,1 8,2 4,1 9,3 3.若10个长方形两两不同，那么面积最小就是取上述前十个长方形面积之和，而此时的面积 为l+2+3+4+4+5 + 6+6+7+8 = 4645.所以必有两个相同的.9.首先，一共有40对小方格，而每对小方格数字之和最小为1+1=2,最大为20+20=40,所 以共39种可能，即39个抽屉，将40个小方格之和放入39个抽屉中，根据抽屉原理，必有 两对小方格数字之和相等.练习4.2L如图所示进行染色，若能剪出题中要求的七个矩形，那么它

11、们必然是由一黑一白两个方程 组成，因此有7黑7白共14个方程.但是图中是8黑6白，矛盾.所以总是剪不出符合题意得七个矩形.2 .提示：证明方法同例6,认识的人连红线，不认识的人连蓝线即可.3 .按图示的方法进行黑白染色.则小虫没走一步必定从一种颜色走到另一个颜色，而第一行和第五行第五列的格子都是黑 色，所以必定要走到偶数步.4 .对象棋盘上每个格点(i,j)赋值马每跳一步，必在行和列中，一种增减2, 一种 增减1,即乘以(一I)?* =一1.所以跳了左步后，到它相邻的格点时，必有(T产(T)J(T产即)JT故女为奇数，命题得证.5 .分析：若只用黑白色染色很难解决问题，所以考虑到可以多重分类，

12、也就是对各个方块进 行标号分类.如图，标上1-4,这些数，显然每个1x4长方块都恰好占据123,4各一个，于是如果可以覆 盖，那么它们应该一样多，但这里有1有25个，2有26个，矛盾，所以不能覆盖.1234123412234123412334563456344321432143I234I234I2234I234I2334563456344321432143I234I2341223412341236 .把这些小三角形的边进行赋值，边的端点同色的，赋值0,边的端点不同，赋值1,于是 每个三角形的三边之和有如下三种情形：(1)三顶点都不同色的，和为3.(2)恰有两个顶点同色的，和为2；(3)三顶点都

13、同色，和为0.设所有小正方形都赋值的和当中，除了 A8,8C,C4边外，其余的边都被算了两次，所以他们的赋值之和为偶数，在加上AB,BC,C4三边赋值之和为3,所以SS是奇数.练习4.31 .不是5的倍数的整数按余数分类可以分四类，即余数分别为123,4,所以有如下分类情形.(1)当 = 5n + l 时，n2 = 5(5m2 + 2m) +1 ,不是 5 的倍数；当 = 5m + 2时，=5(5+4+ 4,不是5的倍数；(3)当 =5m + 3 时，=5(5 机 2+6 + 1) + 4,不是 5 的倍数；(4)当 = 5m + 4时，=5(5w2+8w + 3) + 1,不是 5 的倍数； 综合可知，命题成立.2 .分析：显然要考虑最大的数5的位置，如果它在中间，会与题意矛盾.因为每个数都不大于 其他两侧数的平均数，所以5一定在最前面或者最后，同理，在这剩下的4个数中，4也必 须在这四个数最前或最后；在这剩下的3个数中，3也必须在这四个数最前或最后；枚举如下：51234, 52134, 53124, 53214, 54123, 54213, 54312, 54321, 12345, 21345, 31245, 32145, 41235, 42135, 43125 共