专题：染色问题与染色方法.doc

蚂膂羀竞赛讲座14膈蚆袆-染色问题与染色方法肄薁螆羈蒃蚁1. -1(a),:存在一个矩形, 由抽屉原则,第1行的7个小方格至少有4个不同色,不妨设为红色(带阴影)并在1、2、3、4列(如图29-1(b)).蚄衿蒀在第1、2、3、4列(以下不必再考虑第5,6,7列)中,如第2行或第3行出现两个红色小方格,则这个问题已经得证;如第2行和第3行每行最多只有一个红色小方格(如图29-1(c)),那么在这两行中必出现四角同为蓝色的矩形,:(1)在上面证明过程中除了运用抽屉原则外,还要用到一种思考问题的有效方法,就是逐步缩小所要讨论的对象的范围,(2)-,        (第2届全国部分省市初中数学通讯赛题)证明:用15块大小是4×1的矩形瓷砖和1块大小是2×2的矩形瓷砖,不能恰好铺盖8× 将8×8矩形地面的一半染上一种颜色,另一半染上另一种颜色,再用4×1和2×2的矩形瓷砖去盖,如果盖住的两种颜色的小矩形不是一样多, 如图29-3,用间隔为两格且与副对角线平行的斜格同色的染色方式,,地面上黑、×1的矩形砖不论是横放还是竖盖,且不论盖在何处,总是占据地面上的两个白格、两个黑格,故15块4×,而与主对角线平行的相邻格总是异色,所以,不论怎样放置,一块2×2的矩形砖,×.  莁袁羁袇莅螇例3        (1986年北京初二数学竞赛题)如图29-4(1)是4个1×1的正方形组成的“L”形,用若干个这种“L”形硬纸片无重迭拼成一个m×n(长为m个单位,宽为n个单位)的矩形如图29-4(2).∵m×n矩形由“L”形拼成,∴m×n是4的倍数,∴m、n中必有一个是偶数,×n矩形中的m列按一列黑、一列白间隔染色(如图29-4(2)),则不论“L”形在这矩形中的放置位置如何(“L”形的放置,共有8种可能),“L”形或占有3白一黑四个单位正方形(第一种),或占有3黑一白四个单位正方形(第二种).薇蒆蚂设第一种“L”形共有p个,第二种“L”形共q个,则m×n矩形中的白格单位正方形数为3p+q,而它的黑格单位正方形数为p+∵m为偶数,∴m×n矩形中黑、白条数相同,黑、+q=p+3q,从而p=“L”形的总数为2p个,即“L”形总数为偶数,所以m×n一定是8的倍数.    莇芄衿膄聿袆2. (1)   “边染色”(或称“线段染色”),        (1947年匈牙利数学奥林匹克试题)世界上任何六个人中,,而来看与之等价的下述命题蕿膄薁例5        (1953年美国普特南数学竞赛题)空间六点,任三点不共线,任四点不共面,成对地连接它们得十五条线段,用红色或蓝色染这些线段(一条线段只染一种颜色).求证:无论怎样染, 设A、B、C、D、E、、AC、AD、AE、AF,由抽屉原则这五条线段中至少有三条颜色相同,不妨设就是AB、AC、AD,△BCD的三边,如其中有一条边例如BC是红色的,则同色三角形已出现(红色△ABC);如△BCD三边都不是红色的,则它就是蓝色的三角形,,不论在哪种情况下,,两人认识的连红线,不认识的连蓝线,