2012江苏省数学竞赛《提优教程》教案第14讲染色问题

第14讲染色问题本节主要讲述用染色的方法解有关的竞赛题．染色，是一种辅助解题的手段，通过染色，把研究对象分类标记，以便直观形象地解决问题，因此染色就是分类的思想的具体化，例如染成两种颜色，就可以看成是奇偶分析的一种表现形式．染色，也是构造抽屉的一个重要方法，利用染色分类，从而构造出抽屉，用抽屉原理来解题．A类例题例1⑴有一个6×6的棋盘，剪去其左上角和右下角各一个小格(边长为1)后，剩下的图形能不能剪成17个1×2的小矩形？⑵剪去国际象棋棋盘左上角2×2的正方形后，能不能用15个由四个格子组成的L形完全覆盖？分析把棋盘的格子用染色分成两类，由此说明留下的图形不能满足题目的要求．证明⑴如图，把6×6棋盘相间染成黑、白二色，使相邻两格染色不同．则剪去的两格同色．但每个1×2小矩形都由一个白格一个黑格组成，故不可能把剩下的图形剪成17个1×2矩形．⑵如图，把8×8方格按列染色，第1，3，5，7列染黑，第2、4、6、8列染白．这样染色，其中黑格有偶数个．由于每个L形盖住三黑一白或三白一黑，故15个L形一定盖住奇数个黑格，故不可能．说明用不同的染色方法解决不同的问题．例2用若干个由四个单位正方形组成的“L”形纸片无重叠地拼成一个mn的矩形，则mn必是8的倍数．分析易证mn是4的倍数，再用染色法证mn是8的倍数．证明：每个L形有4个方格，故4|mn．于是m、n中至少有一个为偶数．设列数n为偶数，则按奇数列染红，偶数列染蓝．于是红格与蓝格各有12mn个，而12mn是偶数．每个L形或盖住3红1蓝，或盖住1红3蓝，设前者有p个，后者有q个．于是红格共盖住3p+q个即p+q为偶数，即有偶数个L形．设有2k个L形．于是mn=2k×4=8k．故证．例1(2)例1(！)说明奇偶分析与染色联合运用解决本题．情景再现1．下面是俄罗斯方块的七个图形：请你用它们拼出(A)图，再用它们拼出(B)图(每块只能用一次，并且不准翻过来用)．如果能拼出来，就在图形上画出拼法，并写明七个图形的编号；如果不能拼出来，就说明理由．2．能否用图中各种形状的纸片（不能剪开）拼成一个边长为75的正方形？（图中每个小方格的边长都为1）请说明理由．B类例题例3⑴以任意方式对平面上的每一点染上红色或者蓝色．证明：一定存在无穷条长为1的线段，这些线段的端点为同一颜色．⑵以任意方式对平面上的每一点染上红色或者蓝色．证明：存在同色的三点，且其中一点为另两点中点．分析任意染色而又要求出现具有某种性质的图形，这是染色问题常见的题型，常用抽屉原理或设置两难命题的方法解．证明⑴取边长为1的等边三角形，其三个顶点中必有两个顶点同色．同色两顶点连成线段即为一条满足要求的线段，由于边长为1的等边三角形有无数个，故满足要求的线段有无数条．⑵取同色两点A、B，延长AB到点C，使BC=AB，再延长BA到点D，使AD=AB，若C、D中有一点为红色，例如点C为红色，则点B为AC中点．则命题成立．否则，C、D全蓝，考虑AB中点M，它也是CD中点．故无论M染红还是蓝，均得证．说明⑴中，两种颜色就是两个“抽屉”，三个点就是三个“苹果”，于是根据抽屉原理，必有两个点落入同一抽屉．⑵中，这里实际上构造了一个两难命题：非此即彼，二者必居其一．让同一点既是某两个红点的中点，又是两个蓝点的中点，从而陷入两难选择的境地，于是满足条件的图形必然(5)(6)(7)(4)(2)(3)(1)(B)(A)存在．达到证明的目的．例4⑴以任意方式对平面上的每一点染上红色或者蓝色．证明：一定可以找到无穷多个顶点为为同一种颜色的等腰三角形．⑵以任意方式对平面上的每一点染上红色或者蓝色．证明：一定可以找到无穷多个顶点为为同一种颜色的等腰直角三角形．分析⑴同样可以设置两难命题：由于等腰三角形的顶点在底边的垂直平分线上，故先选两个同色点连成底边，再在连线的垂直平分线上找同色的点，这是解法1的思路．利用圆的半径相等来构造等腰三角形的两腰，这是解法2的思路．利用抽屉原理，任5个点中必有三点同色，只要这5点中任三点都是一个等腰三角形的顶点即可，而正五边形的五个顶点中任三个都是等腰三角形的顶点，这是解法3的思路．⑵连正方形的对角线即得到两个等腰直角三角形，所以从正方形入手解决相题第2问．⑴证明1任取两个同色点A、B(设同红)，作AB的垂直平分线MN，若MN上(除与AB交点外)有红色点，则有红色三角形，若无红色点，则MN上至多一个红点其余均蓝，取关于AB对称的两点C、D，均蓝．则若AB上有(除交点外)蓝点，则有蓝色三角形，若无蓝点，则在矩形EFGH内任取一点K(不在边上)若K为蓝，则可在CD上取两点与之构成蓝色三角形，若K为红，则可在AB上找到两点与之构成红色三角形．证明2任取一红点O，以O为圆心任作一圆，若此圆上有不是同一直径端点的两个红点A、B，则出现红色顶点等腰三角形OAB，若圆上只有一个红点或只有同一直径的两个端点是红点，则圆上有无数蓝点，取两个蓝点(不关于红点为端点的直径对称)C、D，于是CD的垂直平分线与圆的两个交点E、F为蓝点，于是存在蓝色顶点的等腰三角形CDE．证明3取一个正五边形ABCDE，根据抽屉原理，它的5个顶点中，必有三个顶点(例如A、B、C)同色，则△ABC即为等腰三角形．⑵证明任取两个蓝点A、B，以AB为一边作正方形ABCD，若C、D有一为蓝色，则出现蓝色三角形．若C、D均红，则对角线交点E或红或蓝，出现红色或蓝色等腰直角三角形．显然按此作法可以得到无数个等腰直角三角形．(由本题也可以证明上一题．)例5设平面上给出了有限个点(不少于五点)的集合S，其中若干个点被染成红色，其余点被染成蓝色，且任意三个同色点不共线．求证：存在一个三角形，具有下述性质：⑴以S中的三个同色点为顶点；⑵此三角形至少有一条边上不含另一种颜色的点．分析要证明存在同色三角形不难，而要满足第⑵个条件，可以用最小数原理．证明由于S中至少有五点，这些点染成两种颜色，故必存在三点同色．且据已知，此三点不共线，故可连成三角形．取所有同色三角形，由于S只有有限个点，从而能连出的同色三角形只有有限个，故其ABCDEKHGFENMDCBA(2)(1)FEDCOBAOABOCDE中必有面积最小的．其中面积最小的三角形即为所求．首先，这个三角形满足条件⑴，其次，若其三边上均有另一种颜色的点，则此三点必可连出三角形，此连出三角形面积更小，矛盾．说明最小数原理，即极端原理．见第十二讲．例6将平面上的每个点都染上红、蓝二色之一，证明：存在两个相似的三角形，其相似比为1995，且每一个三角形的三个顶点同色．(1995年全国联赛加试题)分析把相似三角形特殊化，变成证明相似的直角三角形，在矩形的网格中去找相似的直角三角形，这是证法1的思路．证法2则是研究形状更特殊的直角三角形：含一个角为30˚的直角三角形．证明可以找到任意边长的这样的三角形，于是对任意的相似比，本题均可证．证法3则是考虑两个同心圆上三条半径交圆得的三组对应点连出的两个三角形一定相似，于是只要考虑找同心圆上的同色点，而要得到3个同色点，只要任取5个只染了两种颜色的点就行；而要得到5个同色点，则只要取9个只染了两种颜色的点即行．证明1首先证明平面上一定存在三个顶点同色的直角三角形．任取平面上的一条直线l，则直线l上必有两点同色．设此两点为P、Q，不妨设P、Q同着红色．过P、Q作直线l的垂线l1、l2，若l1或l2上有异于P、Q的点着红色，则存在红色直角三角形．若l1、l2上除P、Q外均无红色点，则在l1上任取异于P的两点R、S，则R、S必着蓝色，过R作l1的垂线交l2于T，则T必着蓝色．△RST即为三顶点同色的直角三角形．下面再证明存在两个相似比为1995的相似的直角三角形．设直角三角形ABC三顶点同色(∠B为直角)．把△ABC补成矩形ABCD(如图)．把矩形的每边都分成n等分(n为正奇数，n1，本题中取n=1995)．连结对边相应分点，把矩形ABCD分成n2个小矩形．AB边上的分点共有n+1个，由于n为奇数，故必存在其中两个相邻的分点同色，(否则任两个相邻分点异色，则可得A、B异色)，不妨设相邻分点E、F同色．考察E、F所在的小矩形的另两个顶点E、F，若E、F异色，则△EFE或△DFF为三个顶点同色的小直角三角形．若E、F同色，再考察以此二点为顶点而在其左边的小矩形，…．这样依次考察过去，不妨设这一行小矩形的每条竖边的两个顶点都同色．同样，BC边上也存在两个相邻的顶点同色，设为P、Q，则考察PQ所在的小矩形，同理，若P、Q所在小矩形的另一横边两个顶点异色，则存在三顶点同色的小直角三角形．否则，PQ所在列的小矩形的每条横边两个顶点都同色．现考察EF所在行与PQ所在列相交的矩形GHNM，如上述，M、H都与N同色，△MNH为顶点同色的直角三角形．由n=1995，故△MNH∽△ABC，且相似比为1995，且这两个直角三角形的顶点分别同色．证明2首先证明：设a为任意正实数，存在距离为2a的同色两点．任取一点O(设为红色点)，以O为圆心，2a为半径作圆，若圆上有一个红点，则存在距离为2a的两个红点，若圆上没有红点，则任一圆内接六边形ABCDEF的六个顶点均为蓝色，但此六边形边长为2a．故存在距离为2a的两个蓝色点．下面证明：存在边长为a，3a，2a的直角三角形，其三个顶点同色．如上证，存在距离为2a的同色两点A、B(设为红点)，Tl2l1PQRSlE'F'HGMNQPEFBCDAFEDCBA以AB为直径作圆，并取圆内接六边形ACDBEF，若C、D、E、F中有任一点为红色，则存在满足要求的红色三角形．若C、D、E、F为蓝色，则存在满足要求的蓝色三角形．下面再证明本题：由上证知，存在边长为a，3a，2a及1995a，19953a，19952a的两个同色三角形，满足要求．证明3以任一点O为圆心，a及1995a为半径作两个同心圆，在小圆上任取9点，其中必有5点同色，设为A、B、C、D、E，作射线OA、OB、OC、OD、OE，交大圆于A，B，C，D，E，则此五点中必存在三点同色，设为A、B、C．则ABC与ABC为满足要求的三角形．情景再现3．以任意方式对平面上的每一点染上红色或者蓝色．证明：一定存在一个矩形，它的四个顶点同色．4．以任意方式对平面上的每一点染上红色或者蓝色．证明：一定可以找到无穷多个顶点全为同一种颜色的全等三角形．5．图中是一个6×6的方格棋盘，现将部分1×1小方格涂成红色。如果随意划掉3行3列，都要使得剩下的方格中一定有一个是红色的，那么至少要涂多少个方格？6．有两个同心圆，圆上的每个点都用红、蓝、黄三色之一染色．试证明：可以分别在每个圆上找到同色的三个点连成圆的内接三角形，且这两个三角形相似．C类例题例7把平面上每个点都以红、黄两色之一着色．求证：一定存在一个边长为1或3的正三角形，它的三个顶点是同色的．分析边长为1及3的三角形在半径为1的圆内接正六边形中出现，故应设法在这样的圆内接正六边形内找满足要求的三角形．以红点M为圆心，1为半径作圆，6等分此圆，若其中没有红点，则存在边长为3的黄顶点三角形，若有红点R，则与之相邻的两分点中有红点则有边长为1的红顶点三角形，若与R相邻的两分点均黄，则考虑直径RQ的另一端点Q，若为黄则可证．故应相距为2的两点R、Q，这样就可构造两难命题了．证明：1˚任取一染成红色的点P，以P为圆心，1为半径作圆，如果圆上及圆内的点都是红色，则存在边长为1及3的三角形，其三个顶点同为红色．若圆上及圆内的点不全染成红色．则存在圆上或圆内一染成黄色的点Q，|PQ|≤1．作△PQR，使PR=QR=2，则R必与P、Q之一染色不同．设R与Q染色不同，即R染红色．2˚取QR中点M，则M必与Q、R之一同色．设与R同色，即同为红色．以RM=1为一边，作正三角形△RMS、△RMT．若S、T中任一点染红，则存在边长为1的红色顶点三角形．若S、T都为黄色，则与Q组成边长为3的黄色顶点三角形．说明把问题归结为相距为2的异色两点．例8在一张100100的方格纸内，能否把数字0，1